Full source code is available on github.
There are several major source files for the C++ version of QQWing:
/*
* qqwing - Sudoku solver and generator
* Copyright (C) 2006-2014 Stephen Ostermiller http://ostermiller.org/
* Copyright (C) 2007 Jacques Bensimon (jacques@ipm.com)
* Copyright (C) 2011 Jean Guillerez (j.guillerez - orange.fr)
* Copyright (C) 2014 Michael Catanzaro (mcatanzaro@gnome.org)
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License along
* with this program; if not, write to the Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/
#include "config.h"
#include <cstdlib>
#include <iostream>
#include "qqwing.hpp"
namespace qqwing {
string getVersion(){
return 1.3.4;
}
/**
* While solving the puzzle, log steps taken in a log item.
* This is useful for later printing out the solve history
* or gathering statistics about how hard the puzzle was to
* solve.
*/
class LogItem {
public:
enum LogType {
GIVEN,
SINGLE,
HIDDEN_SINGLE_ROW,
HIDDEN_SINGLE_COLUMN,
HIDDEN_SINGLE_SECTION,
GUESS,
ROLLBACK,
NAKED_PAIR_ROW,
NAKED_PAIR_COLUMN,
NAKED_PAIR_SECTION,
POINTING_PAIR_TRIPLE_ROW,
POINTING_PAIR_TRIPLE_COLUMN,
ROW_BOX,
COLUMN_BOX,
HIDDEN_PAIR_ROW,
HIDDEN_PAIR_COLUMN,
HIDDEN_PAIR_SECTION
};
LogItem(int round, LogType type);
LogItem(int round, LogType type, int value, int position);
int getRound();
void print();
LogType getType();
~LogItem();
private:
void init(int round, LogType type, int value, int position);
/**
* The recursion level at which this item was gathered.
* Used for backing out log items solve branches that
* don't lead to a solution.
*/
int round;
/**
* The type of log message that will determine the
* message printed.
*/
LogType type;
/**
* Value that was set by the operation (or zero for no value)
*/
int value;
/**
* position on the board at which the value (if any) was set.
*/
int position;
};
void shuffleArray(int* array, int size);
SudokuBoard::Symmetry getRandomSymmetry();
int getLogCount(vector<LogItem*>* v, LogItem::LogType type);
static inline int cellToColumn(int cell);
static inline int cellToRow(int cell);
static inline int cellToSectionStartCell(int cell);
static inline int cellToSection(int cell);
static inline int rowToFirstCell(int row);
static inline int columnToFirstCell(int column);
static inline int sectionToFirstCell(int section);
static inline int getPossibilityIndex(int valueIndex, int cell);
static inline int rowColumnToCell(int row, int column);
static inline int sectionToCell(int section, int offset);
/**
* Create a new Sudoku board
*/
SudokuBoard::SudokuBoard() :
puzzle ( new int[BOARD_SIZE] ),
solution ( new int[BOARD_SIZE] ),
solutionRound ( new int[BOARD_SIZE] ),
possibilities ( new int[POSSIBILITY_SIZE] ),
randomBoardArray ( new int[BOARD_SIZE] ),
randomPossibilityArray ( new int[ROW_COL_SEC_SIZE] ),
recordHistory ( false ),
logHistory( false ),
solveHistory ( new vector<LogItem*>() ),
solveInstructions ( new vector<LogItem*>() ),
printStyle ( READABLE ),
lastSolveRound (0)
{
{for (int i=0; i<BOARD_SIZE; i++){
randomBoardArray[i] = i;
}}
{for (int i=0; i<ROW_COL_SEC_SIZE; i++){
randomPossibilityArray[i] = i;
}}
}
/**
* Get the number of cells that are
* set in the puzzle (as opposed to
* figured out in the solution
*/
int SudokuBoard::getGivenCount(){
int count = 0;
{for (int i=0; i<BOARD_SIZE; i++){
if (puzzle[i] != 0) count++;
}}
return count;
}
/**
* Set the board to the given puzzle.
* The given puzzle must be an array of 81 integers.
*/
bool SudokuBoard::setPuzzle(int* initPuzzle){
{for (int i=0; i<BOARD_SIZE; i++){
puzzle[i] = (initPuzzle==NULL)?0:initPuzzle[i];
}}
return reset();
}
/**
* Retrieves the puzzle as an unmodifiable array of 81 integers.
*/
const int* SudokuBoard::getPuzzle(){
return puzzle;
}
/**
* Retrieves the puzzle's solution as an unmodifiable array of 81 integers.
*/
const int* SudokuBoard::getSolution(){
return solution;
}
/**
* Reset the board to its initial state with
* only the givens.
* This method clears any solution, resets statistics,
* and clears any history messages.
*/
bool SudokuBoard::reset(){
{for (int i=0; i<BOARD_SIZE; i++){
solution[i] = 0;
}}
{for (int i=0; i<BOARD_SIZE; i++){
solutionRound[i] = 0;
}}
{for (int i=0; i<POSSIBILITY_SIZE; i++){
possibilities[i] = 0;
}}
{for (unsigned int i=0; i<solveHistory->size(); i++){
delete solveHistory->at(i);
}}
solveHistory->clear();
solveInstructions->clear();
int round = 1;
for (int position=0; position<BOARD_SIZE; position++){
if (puzzle[position] > 0){
int valIndex = puzzle[position]-1;
int valPos = getPossibilityIndex(valIndex,position);
int value = puzzle[position];
if (possibilities[valPos] != 0) return false;
mark(position,round,value);
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::GIVEN, value, position));
}
}
return true;
}
/**
* Get the difficulty rating.
*
* This method will return SudokuBoard::UNKNOWN unless
* a puzzle has been generated or set and then the following methods called:
* setRecordHistory(true), and solve()
*/
SudokuBoard::Difficulty SudokuBoard::getDifficulty(){
if (getGuessCount() > 0) return SudokuBoard::EXPERT;
if (getBoxLineReductionCount() > 0) return SudokuBoard::INTERMEDIATE;
if (getPointingPairTripleCount() > 0) return SudokuBoard::INTERMEDIATE;
if (getHiddenPairCount() > 0) return SudokuBoard::INTERMEDIATE;
if (getNakedPairCount() > 0) return SudokuBoard::INTERMEDIATE;
if (getHiddenSingleCount() > 0) return SudokuBoard::EASY;
if (getSingleCount() > 0) return SudokuBoard::SIMPLE;
return SudokuBoard::UNKNOWN;
}
/**
* Get the difficulty rating.
*
* This method will return "Unknown" unless
* a puzzle has been generated or set and then the following methods called:
* setRecordHistory(true), and solve()
*/
string SudokuBoard::getDifficultyAsString(){
SudokuBoard::Difficulty difficulty = getDifficulty();
switch (difficulty){
case SudokuBoard::EXPERT: return "Expert";
case SudokuBoard::INTERMEDIATE: return "Intermediate";
case SudokuBoard::EASY: return "Easy";
case SudokuBoard::SIMPLE: return "Simple";
default: return "Unknown";
}
}
/**
* Get the number of cells for which the solution was determined
* because there was only one possible value for that cell.
*/
int SudokuBoard::getSingleCount(){
return getLogCount(solveInstructions, LogItem::SINGLE);
}
/**
* Get the number of cells for which the solution was determined
* because that cell had the only possibility for some value in
* the row, column, or section.
*/
int SudokuBoard::getHiddenSingleCount(){
return getLogCount(solveInstructions, LogItem::HIDDEN_SINGLE_ROW) +
getLogCount(solveInstructions, LogItem::HIDDEN_SINGLE_COLUMN) +
getLogCount(solveInstructions, LogItem::HIDDEN_SINGLE_SECTION);
}
/**
* Get the number of naked pair reductions that were performed
* in solving this puzzle.
*/
int SudokuBoard::getNakedPairCount(){
return getLogCount(solveInstructions, LogItem::NAKED_PAIR_ROW) +
getLogCount(solveInstructions, LogItem::NAKED_PAIR_COLUMN) +
getLogCount(solveInstructions, LogItem::NAKED_PAIR_SECTION);
}
/**
* Get the number of hidden pair reductions that were performed
* in solving this puzzle.
*/
int SudokuBoard::getHiddenPairCount(){
return getLogCount(solveInstructions, LogItem::HIDDEN_PAIR_ROW) +
getLogCount(solveInstructions, LogItem::HIDDEN_PAIR_COLUMN) +
getLogCount(solveInstructions, LogItem::HIDDEN_PAIR_SECTION);
}
/**
* Get the number of pointing pair/triple reductions that were performed
* in solving this puzzle.
*/
int SudokuBoard::getPointingPairTripleCount(){
return getLogCount(solveInstructions, LogItem::POINTING_PAIR_TRIPLE_ROW)+
getLogCount(solveInstructions, LogItem::POINTING_PAIR_TRIPLE_COLUMN);
}
/**
* Get the number of box/line reductions that were performed
* in solving this puzzle.
*/
int SudokuBoard::getBoxLineReductionCount(){
return getLogCount(solveInstructions, LogItem::ROW_BOX)+
getLogCount(solveInstructions, LogItem::COLUMN_BOX);
}
/**
* Get the number lucky guesses in solving this puzzle.
*/
int SudokuBoard::getGuessCount(){
return getLogCount(solveInstructions, LogItem::GUESS);
}
/**
* Get the number of backtracks (unlucky guesses) required
* when solving this puzzle.
*/
int SudokuBoard::getBacktrackCount(){
return getLogCount(solveHistory, LogItem::ROLLBACK);
}
void SudokuBoard::shuffleRandomArrays(){
shuffleArray(randomBoardArray, BOARD_SIZE);
shuffleArray(randomPossibilityArray, ROW_COL_SEC_SIZE);
}
void SudokuBoard::clearPuzzle(){
// Clear any existing puzzle
{for (int i=0; i<BOARD_SIZE; i++){
puzzle[i] = 0;
}}
reset();
}
bool SudokuBoard::generatePuzzle(){
return generatePuzzleSymmetry(SudokuBoard::NONE);
}
bool SudokuBoard::generatePuzzleSymmetry(SudokuBoard::Symmetry symmetry){
if (symmetry == SudokuBoard::RANDOM) symmetry = getRandomSymmetry();
// Don't record history while generating.
bool recHistory = recordHistory;
setRecordHistory(false);
bool lHistory = logHistory;
setLogHistory(false);
clearPuzzle();
// Start by getting the randomness in order so that
// each puzzle will be different from the last.
shuffleRandomArrays();
// Now solve the puzzle the whole way. The solve
// uses random algorithms, so we should have a
// really randomly totally filled sudoku
// Even when starting from an empty grid
solve();
if (symmetry == SudokuBoard::NONE){
// Rollback any square for which it is obvious that
// the square doesn't contribute to a unique solution
// (ie, squares that were filled by logic rather
// than by guess)
rollbackNonGuesses();
}
// Record all marked squares as the puzzle so
// that we can call countSolutions without losing it.
{for (int i=0; i<BOARD_SIZE; i++){
puzzle[i] = solution[i];
}}
// Rerandomize everything so that we test squares
// in a different order than they were added.
shuffleRandomArrays();
// Remove one value at a time and see if
// the puzzle still has only one solution.
// If it does, leave it out the point because
// it is not needed.
{for (int i=0; i<BOARD_SIZE; i++){
// check all the positions, but in shuffled order
int position = randomBoardArray[i];
if (puzzle[position] > 0){
int positionsym1 = -1;
int positionsym2 = -1;
int positionsym3 = -1;
switch (symmetry){
case ROTATE90:
positionsym2 = rowColumnToCell(ROW_COL_SEC_SIZE-1-cellToColumn(position),cellToRow(position));
positionsym3 = rowColumnToCell(cellToColumn(position),ROW_COL_SEC_SIZE-1-cellToRow(position));
case ROTATE180:
positionsym1 = rowColumnToCell(ROW_COL_SEC_SIZE-1-cellToRow(position),ROW_COL_SEC_SIZE-1-cellToColumn(position));
break;
case MIRROR:
positionsym1 = rowColumnToCell(cellToRow(position),ROW_COL_SEC_SIZE-1-cellToColumn(position));
break;
case FLIP:
positionsym1 = rowColumnToCell(ROW_COL_SEC_SIZE-1-cellToRow(position),cellToColumn(position));
break;
case RANDOM: // NOTE: Should never happen
break;
case NONE: // NOTE: No need to do anything
break;
}
// try backing out the value and
// counting solutions to the puzzle
int savedValue = puzzle[position];
puzzle[position] = 0;
int savedSym1 = 0;
if (positionsym1 >= 0){
savedSym1 = puzzle[positionsym1];
puzzle[positionsym1] = 0;
}
int savedSym2 = 0;
if (positionsym2 >= 0){
savedSym2 = puzzle[positionsym2];
puzzle[positionsym2] = 0;
}
int savedSym3 = 0;
if (positionsym3 >= 0){
savedSym3 = puzzle[positionsym3];
puzzle[positionsym3] = 0;
}
reset();
if (countSolutions(2, true) > 1){
// Put it back in, it is needed
puzzle[position] = savedValue;
if (positionsym1 >= 0 && savedSym1 != 0) puzzle[positionsym1] = savedSym1;
if (positionsym2 >= 0 && savedSym2 != 0) puzzle[positionsym2] = savedSym2;
if (positionsym3 >= 0 && savedSym3 != 0) puzzle[positionsym3] = savedSym3;
}
}
}}
// Clear all solution info, leaving just the puzzle.
reset();
// Restore recording history.
setRecordHistory(recHistory);
setLogHistory(lHistory);
return true;
}
void SudokuBoard::rollbackNonGuesses(){
// Guesses are odd rounds
// Non-guesses are even rounds
{for (int i=2; i<=lastSolveRound; i+=2){
rollbackRound(i);
}}
}
void SudokuBoard::setPrintStyle(PrintStyle ps){
printStyle = ps;
}
void SudokuBoard::setRecordHistory(bool recHistory){
recordHistory = recHistory;
}
void SudokuBoard::setLogHistory(bool logHist){
logHistory = logHist;
}
void SudokuBoard::addHistoryItem(LogItem* l){
if (logHistory){
l->print();
cout << endl;
}
if (recordHistory){
solveHistory->push_back(l);
solveInstructions->push_back(l);
} else {
delete l;
}
}
void SudokuBoard::printHistory(vector<LogItem*>* v){
if (!recordHistory){
cout << "History was not recorded.";
if (printStyle == CSV){
cout << " -- ";
} else {
cout << endl;
}
}
{for (unsigned int i=0;i<v->size();i++){
cout << i+1 << ". ";
v->at(i)->print();
if (printStyle == CSV){
cout << " -- ";
} else {
cout << endl;
}
}}
if (printStyle == CSV){
cout << ",";
} else {
cout << endl;
}
}
void SudokuBoard::printSolveInstructions(){
if (isSolved()){
printHistory(solveInstructions);
} else {
cout << "No solve instructions - Puzzle is not possible to solve." << endl;
}
}
void SudokuBoard::printSolveHistory(){
printHistory(solveHistory);
}
bool SudokuBoard::solve(){
reset();
shuffleRandomArrays();
return solve(2);
}
bool SudokuBoard::solve(int round){
lastSolveRound = round;
while (singleSolveMove(round)){
if (isSolved()) return true;
if (isImpossible()) return false;
}
int nextGuessRound = round+1;
int nextRound = round+2;
for (int guessNumber=0; guess(nextGuessRound, guessNumber); guessNumber++){
if (isImpossible() || !solve(nextRound)){
rollbackRound(nextRound);
rollbackRound(nextGuessRound);
} else {
return true;
}
}
return false;
}
bool SudokuBoard::hasNoSolution(){
return countSolutionsLimited() == 0;
}
bool SudokuBoard::hasUniqueSolution(){
return countSolutionsLimited() == 1;
}
bool SudokuBoard::hasMultipleSolutions(){
return countSolutionsLimited() > 1;
}
int SudokuBoard::countSolutions(){
return countSolutions(false);
}
int SudokuBoard::countSolutionsLimited(){
return countSolutions(true);
}
int SudokuBoard::countSolutions(bool limitToTwo){
// Don't record history while generating.
bool recHistory = recordHistory;
setRecordHistory(false);
bool lHistory = logHistory;
setLogHistory(false);
reset();
int solutionCount = countSolutions(2, limitToTwo);
// Restore recording history.
setRecordHistory(recHistory);
setLogHistory(lHistory);
return solutionCount;
}
int SudokuBoard::countSolutions(int round, bool limitToTwo){
while (singleSolveMove(round)){
if (isSolved()){
rollbackRound(round);
return 1;
}
if (isImpossible()){
rollbackRound(round);
return 0;
}
}
int solutions = 0;
int nextRound = round+1;
for (int guessNumber=0; guess(nextRound, guessNumber); guessNumber++){
solutions += countSolutions(nextRound, limitToTwo);
if (limitToTwo && solutions >=2){
rollbackRound(round);
return solutions;
}
}
rollbackRound(round);
return solutions;
}
void SudokuBoard::rollbackRound(int round){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::ROLLBACK));
{for (int i=0; i<BOARD_SIZE; i++){
if (solutionRound[i] == round){
solutionRound[i] = 0;
solution[i] = 0;
}
}}
{for (int i=0; i<POSSIBILITY_SIZE; i++){
if (possibilities[i] == round){
possibilities[i] = 0;
}
}}
while(solveInstructions->size() > 0 && solveInstructions->back()->getRound() == round){
solveInstructions->pop_back();
}
}
bool SudokuBoard::isSolved(){
{for (int i=0; i<BOARD_SIZE; i++){
if (solution[i] == 0){
return false;
}
}}
return true;
}
bool SudokuBoard::isImpossible(){
for (int position=0; position<BOARD_SIZE; position++){
if (solution[position] == 0){
int count = 0;
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0) count++;
}
if (count == 0) {
return true;
}
}
}
return false;
}
int SudokuBoard::findPositionWithFewestPossibilities(){
int minPossibilities = 10;
int bestPosition = 0;
{for (int i=0; i<BOARD_SIZE; i++){
int position = randomBoardArray[i];
if (solution[position] == 0){
int count = 0;
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0) count++;
}
if (count < minPossibilities){
minPossibilities = count;
bestPosition = position;
}
}
}}
return bestPosition;
}
bool SudokuBoard::guess(int round, int guessNumber){
int localGuessCount = 0;
int position = findPositionWithFewestPossibilities();
{for (int i=0; i<ROW_COL_SEC_SIZE; i++){
int valIndex = randomPossibilityArray[i];
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0){
if (localGuessCount == guessNumber){
int value = valIndex+1;
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::GUESS, value, position));
mark(position, round, value);
return true;
}
localGuessCount++;
}
}}
return false;
}
bool SudokuBoard::singleSolveMove(int round){
if (onlyPossibilityForCell(round)) return true;
if (onlyValueInSection(round)) return true;
if (onlyValueInRow(round)) return true;
if (onlyValueInColumn(round)) return true;
if (handleNakedPairs(round)) return true;
if (pointingRowReduction(round)) return true;
if (pointingColumnReduction(round)) return true;
if (rowBoxReduction(round)) return true;
if (colBoxReduction(round)) return true;
if (hiddenPairInRow(round)) return true;
if (hiddenPairInColumn(round)) return true;
if (hiddenPairInSection(round)) return true;
return false;
}
bool SudokuBoard::colBoxReduction(int round){
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
for (int col=0; col<ROW_COL_SEC_SIZE; col++){
int colStart = columnToFirstCell(col);
bool inOneBox = true;
int colBox = -1;
{for (int i=0; i<GRID_SIZE; i++){
for (int j=0; j<GRID_SIZE; j++){
int row = i*GRID_SIZE+j;
int position = rowColumnToCell(row, col);
int valPos = getPossibilityIndex(valIndex,position);
if(possibilities[valPos] == 0){
if (colBox == -1 || colBox == i){
colBox = i;
} else {
inOneBox = false;
}
}
}
}}
if (inOneBox && colBox != -1){
bool doneSomething = false;
int row = GRID_SIZE*colBox;
int secStart = cellToSectionStartCell(rowColumnToCell(row, col));
int secStartRow = cellToRow(secStart);
int secStartCol = cellToColumn(secStart);
{for (int i=0; i<GRID_SIZE; i++){
for (int j=0; j<GRID_SIZE; j++){
int row2 = secStartRow+i;
int col2 = secStartCol+j;
int position = rowColumnToCell(row2, col2);
int valPos = getPossibilityIndex(valIndex,position);
if (col != col2 && possibilities[valPos] == 0){
possibilities[valPos] = round;
doneSomething = true;
}
}
}}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::COLUMN_BOX, valIndex+1, colStart));
return true;
}
}
}
}
return false;
}
bool SudokuBoard::rowBoxReduction(int round){
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
for (int row=0; row<ROW_COL_SEC_SIZE; row++){
int rowStart = rowToFirstCell(row);
bool inOneBox = true;
int rowBox = -1;
{for (int i=0; i<GRID_SIZE; i++){
for (int j=0; j<GRID_SIZE; j++){
int column = i*GRID_SIZE+j;
int position = rowColumnToCell(row, column);
int valPos = getPossibilityIndex(valIndex,position);
if(possibilities[valPos] == 0){
if (rowBox == -1 || rowBox == i){
rowBox = i;
} else {
inOneBox = false;
}
}
}
}}
if (inOneBox && rowBox != -1){
bool doneSomething = false;
int column = GRID_SIZE*rowBox;
int secStart = cellToSectionStartCell(rowColumnToCell(row, column));
int secStartRow = cellToRow(secStart);
int secStartCol = cellToColumn(secStart);
{for (int i=0; i<GRID_SIZE; i++){
for (int j=0; j<GRID_SIZE; j++){
int row2 = secStartRow+i;
int col2 = secStartCol+j;
int position = rowColumnToCell(row2, col2);
int valPos = getPossibilityIndex(valIndex,position);
if (row != row2 && possibilities[valPos] == 0){
possibilities[valPos] = round;
doneSomething = true;
}
}
}}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::ROW_BOX, valIndex+1, rowStart));
return true;
}
}
}
}
return false;
}
bool SudokuBoard::pointingRowReduction(int round){
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
for (int section=0; section<ROW_COL_SEC_SIZE; section++){
int secStart = sectionToFirstCell(section);
bool inOneRow = true;
int boxRow = -1;
for (int j=0; j<GRID_SIZE; j++){
{for (int i=0; i<GRID_SIZE; i++){
int secVal=secStart+i+(ROW_COL_SEC_SIZE*j);
int valPos = getPossibilityIndex(valIndex,secVal);
if(possibilities[valPos] == 0){
if (boxRow == -1 || boxRow == j){
boxRow = j;
} else {
inOneRow = false;
}
}
}}
}
if (inOneRow && boxRow != -1){
bool doneSomething = false;
int row = cellToRow(secStart) + boxRow;
int rowStart = rowToFirstCell(row);
{for (int i=0; i<ROW_COL_SEC_SIZE; i++){
int position = rowStart+i;
int section2 = cellToSection(position);
int valPos = getPossibilityIndex(valIndex,position);
if (section != section2 && possibilities[valPos] == 0){
possibilities[valPos] = round;
doneSomething = true;
}
}}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::POINTING_PAIR_TRIPLE_ROW, valIndex+1, rowStart));
return true;
}
}
}
}
return false;
}
bool SudokuBoard::pointingColumnReduction(int round){
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
for (int section=0; section<ROW_COL_SEC_SIZE; section++){
int secStart = sectionToFirstCell(section);
bool inOneCol = true;
int boxCol = -1;
{for (int i=0; i<GRID_SIZE; i++){
for (int j=0; j<GRID_SIZE; j++){
int secVal=secStart+i+(ROW_COL_SEC_SIZE*j);
int valPos = getPossibilityIndex(valIndex,secVal);
if(possibilities[valPos] == 0){
if (boxCol == -1 || boxCol == i){
boxCol = i;
} else {
inOneCol = false;
}
}
}
}}
if (inOneCol && boxCol != -1){
bool doneSomething = false;
int col = cellToColumn(secStart) + boxCol;
int colStart = columnToFirstCell(col);
{for (int i=0; i<ROW_COL_SEC_SIZE; i++){
int position = colStart+(ROW_COL_SEC_SIZE*i);
int section2 = cellToSection(position);
int valPos = getPossibilityIndex(valIndex,position);
if (section != section2 && possibilities[valPos] == 0){
possibilities[valPos] = round;
doneSomething = true;
}
}}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::POINTING_PAIR_TRIPLE_COLUMN, valIndex+1, colStart));
return true;
}
}
}
}
return false;
}
int SudokuBoard::countPossibilities(int position){
int count = 0;
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0) count++;
}
return count;
}
bool SudokuBoard::arePossibilitiesSame(int position1, int position2){
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
int valPos1 = getPossibilityIndex(valIndex,position1);
int valPos2 = getPossibilityIndex(valIndex,position2);
if ((possibilities[valPos1] == 0 || possibilities[valPos2] == 0) && (possibilities[valPos1] != 0 || possibilities[valPos2] != 0)){
return false;
}
}
return true;
}
bool SudokuBoard::removePossibilitiesInOneFromTwo(int position1, int position2, int round){
bool doneSomething = false;
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
int valPos1 = getPossibilityIndex(valIndex,position1);
int valPos2 = getPossibilityIndex(valIndex,position2);
if (possibilities[valPos1] == 0 && possibilities[valPos2] == 0){
possibilities[valPos2] = round;
doneSomething = true;
}
}
return doneSomething;
}
bool SudokuBoard::hiddenPairInColumn(int round){
for (int column=0; column<ROW_COL_SEC_SIZE; column++){
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
int r1 = -1;
int r2 = -1;
int valCount = 0;
for (int row=0; row<ROW_COL_SEC_SIZE; row++){
int position = rowColumnToCell(row,column);
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0){
if (r1 == -1 || r1 == row){
r1 = row;
} else if (r2 == -1 || r2 == row){
r2 = row;
}
valCount++;
}
}
if (valCount==2){
for (int valIndex2=valIndex+1; valIndex2<ROW_COL_SEC_SIZE; valIndex2++){
int r3 = -1;
int r4 = -1;
int valCount2 = 0;
for (int row=0; row<ROW_COL_SEC_SIZE; row++){
int position = rowColumnToCell(row,column);
int valPos = getPossibilityIndex(valIndex2,position);
if (possibilities[valPos] == 0){
if (r3 == -1 || r3 == row){
r3 = row;
} else if (r4 == -1 || r4 == row){
r4 = row;
}
valCount2++;
}
}
if (valCount2==2 && r1==r3 && r2==r4){
bool doneSomething = false;
for (int valIndex3=0; valIndex3<ROW_COL_SEC_SIZE; valIndex3++){
if (valIndex3 != valIndex && valIndex3 != valIndex2){
int position1 = rowColumnToCell(r1,column);
int position2 = rowColumnToCell(r2,column);
int valPos1 = getPossibilityIndex(valIndex3,position1);
int valPos2 = getPossibilityIndex(valIndex3,position2);
if (possibilities[valPos1] == 0){
possibilities[valPos1] = round;
doneSomething = true;
}
if (possibilities[valPos2] == 0){
possibilities[valPos2] = round;
doneSomething = true;
}
}
}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::HIDDEN_PAIR_COLUMN, valIndex+1, rowColumnToCell(r1,column)));
return true;
}
}
}
}
}
}
return false;
}
bool SudokuBoard::hiddenPairInSection(int round){
for (int section=0; section<ROW_COL_SEC_SIZE; section++){
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
int si1 = -1;
int si2 = -1;
int valCount = 0;
for (int secInd=0; secInd<ROW_COL_SEC_SIZE; secInd++){
int position = sectionToCell(section,secInd);
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0){
if (si1 == -1 || si1 == secInd){
si1 = secInd;
} else if (si2 == -1 || si2 == secInd){
si2 = secInd;
}
valCount++;
}
}
if (valCount==2){
for (int valIndex2=valIndex+1; valIndex2<ROW_COL_SEC_SIZE; valIndex2++){
int si3 = -1;
int si4 = -1;
int valCount2 = 0;
for (int secInd=0; secInd<ROW_COL_SEC_SIZE; secInd++){
int position = sectionToCell(section,secInd);
int valPos = getPossibilityIndex(valIndex2,position);
if (possibilities[valPos] == 0){
if (si3 == -1 || si3 == secInd){
si3 = secInd;
} else if (si4 == -1 || si4 == secInd){
si4 = secInd;
}
valCount2++;
}
}
if (valCount2==2 && si1==si3 && si2==si4){
bool doneSomething = false;
for (int valIndex3=0; valIndex3<ROW_COL_SEC_SIZE; valIndex3++){
if (valIndex3 != valIndex && valIndex3 != valIndex2){
int position1 = sectionToCell(section,si1);
int position2 = sectionToCell(section,si2);
int valPos1 = getPossibilityIndex(valIndex3,position1);
int valPos2 = getPossibilityIndex(valIndex3,position2);
if (possibilities[valPos1] == 0){
possibilities[valPos1] = round;
doneSomething = true;
}
if (possibilities[valPos2] == 0){
possibilities[valPos2] = round;
doneSomething = true;
}
}
}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::HIDDEN_PAIR_SECTION, valIndex+1, sectionToCell(section,si1)));
return true;
}
}
}
}
}
}
return false;
}
bool SudokuBoard::hiddenPairInRow(int round){
for (int row=0; row<ROW_COL_SEC_SIZE; row++){
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
int c1 = -1;
int c2 = -1;
int valCount = 0;
for (int column=0; column<ROW_COL_SEC_SIZE; column++){
int position = rowColumnToCell(row,column);
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0){
if (c1 == -1 || c1 == column){
c1 = column;
} else if (c2 == -1 || c2 == column){
c2 = column;
}
valCount++;
}
}
if (valCount==2){
for (int valIndex2=valIndex+1; valIndex2<ROW_COL_SEC_SIZE; valIndex2++){
int c3 = -1;
int c4 = -1;
int valCount2 = 0;
for (int column=0; column<ROW_COL_SEC_SIZE; column++){
int position = rowColumnToCell(row,column);
int valPos = getPossibilityIndex(valIndex2,position);
if (possibilities[valPos] == 0){
if (c3 == -1 || c3 == column){
c3 = column;
} else if (c4 == -1 || c4 == column){
c4 = column;
}
valCount2++;
}
}
if (valCount2==2 && c1==c3 && c2==c4){
bool doneSomething = false;
for (int valIndex3=0; valIndex3<ROW_COL_SEC_SIZE; valIndex3++){
if (valIndex3 != valIndex && valIndex3 != valIndex2){
int position1 = rowColumnToCell(row,c1);
int position2 = rowColumnToCell(row,c2);
int valPos1 = getPossibilityIndex(valIndex3,position1);
int valPos2 = getPossibilityIndex(valIndex3,position2);
if (possibilities[valPos1] == 0){
possibilities[valPos1] = round;
doneSomething = true;
}
if (possibilities[valPos2] == 0){
possibilities[valPos2] = round;
doneSomething = true;
}
}
}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::HIDDEN_PAIR_ROW, valIndex+1, rowColumnToCell(row,c1)));
return true;
}
}
}
}
}
}
return false;
}
bool SudokuBoard::handleNakedPairs(int round){
for (int position=0; position<BOARD_SIZE; position++){
int possibilities = countPossibilities(position);
if (possibilities == 2){
int row = cellToRow(position);
int column = cellToColumn(position);
int section = cellToSectionStartCell(position);
for (int position2=position; position2<BOARD_SIZE; position2++){
if (position != position2){
int possibilities2 = countPossibilities(position2);
if (possibilities2 == 2 && arePossibilitiesSame(position, position2)){
if (row == cellToRow(position2)){
bool doneSomething = false;
for (int column2=0; column2<ROW_COL_SEC_SIZE; column2++){
int position3 = rowColumnToCell(row,column2);
if (position3 != position && position3 != position2 && removePossibilitiesInOneFromTwo(position, position3, round)){
doneSomething = true;
}
}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::NAKED_PAIR_ROW, 0, position));
return true;
}
}
if (column == cellToColumn(position2)){
bool doneSomething = false;
for (int row2=0; row2<ROW_COL_SEC_SIZE; row2++){
int position3 = rowColumnToCell(row2,column);
if (position3 != position && position3 != position2 && removePossibilitiesInOneFromTwo(position, position3, round)){
doneSomething = true;
}
}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::NAKED_PAIR_COLUMN, 0, position));
return true;
}
}
if (section == cellToSectionStartCell(position2)){
bool doneSomething = false;
int secStart = cellToSectionStartCell(position);
{for (int i=0; i<GRID_SIZE; i++){
for (int j=0; j<GRID_SIZE; j++){
int position3=secStart+i+(ROW_COL_SEC_SIZE*j);
if (position3 != position && position3 != position2 && removePossibilitiesInOneFromTwo(position, position3, round)){
doneSomething = true;
}
}
}}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::NAKED_PAIR_SECTION, 0, position));
return true;
}
}
}
}
}
}
}
return false;
}
/**
* Mark exactly one cell which is the only possible value for some row, if
* such a cell exists.
* This method will look in a row for a possibility that is only listed
* for one cell. This type of cell is often called a "hidden single"
*/
bool SudokuBoard::onlyValueInRow(int round){
for (int row=0; row<ROW_COL_SEC_SIZE; row++){
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
int count = 0;
int lastPosition = 0;
for (int col=0; col<ROW_COL_SEC_SIZE; col++){
int position = (row*ROW_COL_SEC_SIZE)+col;
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0){
count++;
lastPosition = position;
}
}
if (count == 1){
int value = valIndex+1;
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::HIDDEN_SINGLE_ROW, value, lastPosition));
mark(lastPosition, round, value);
return true;
}
}
}
return false;
}
/**
* Mark exactly one cell which is the only possible value for some column, if
* such a cell exists.
* This method will look in a column for a possibility that is only listed
* for one cell. This type of cell is often called a "hidden single"
*/
bool SudokuBoard::onlyValueInColumn(int round){
for (int col=0; col<ROW_COL_SEC_SIZE; col++){
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
int count = 0;
int lastPosition = 0;
for (int row=0; row<ROW_COL_SEC_SIZE; row++){
int position = rowColumnToCell(row,col);
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0){
count++;
lastPosition = position;
}
}
if (count == 1){
int value = valIndex+1;
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::HIDDEN_SINGLE_COLUMN, value, lastPosition));
mark(lastPosition, round, value);
return true;
}
}
}
return false;
}
/**
* Mark exactly one cell which is the only possible value for some section, if
* such a cell exists.
* This method will look in a section for a possibility that is only listed
* for one cell. This type of cell is often called a "hidden single"
*/
bool SudokuBoard::onlyValueInSection(int round){
for (int sec=0; sec<ROW_COL_SEC_SIZE; sec++){
int secPos = sectionToFirstCell(sec);
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
int count = 0;
int lastPosition = 0;
{for (int i=0; i<GRID_SIZE; i++){
for (int j=0; j<GRID_SIZE; j++){
int position = secPos + i + ROW_COL_SEC_SIZE*j;
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0){
count++;
lastPosition = position;
}
}
}}
if (count == 1){
int value = valIndex+1;
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::HIDDEN_SINGLE_SECTION, value, lastPosition));
mark(lastPosition, round, value);
return true;
}
}
}
return false;
}
/**
* Mark exactly one cell that has a single possibility, if such a cell exists.
* This method will look for a cell that has only one possibility. This type
* of cell is often called a "single"
*/
bool SudokuBoard::onlyPossibilityForCell(int round){
for (int position=0; position<BOARD_SIZE; position++){
if (solution[position] == 0){
int count = 0;
int lastValue = 0;
for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0){
count++;
lastValue=valIndex+1;
}
}
if (count == 1){
mark(position, round, lastValue);
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::SINGLE, lastValue, position));
return true;
}
}
}
return false;
}
/**
* Mark the given value at the given position. Go through
* the row, column, and section for the position and remove
* the value from the possibilities.
*
* @param position Position into the board (0-80)
* @param round Round to mark for rollback purposes
* @param value The value to go in the square at the given position
*/
void SudokuBoard::mark(int position, int round, int value){
if (solution[position] != 0) throw ("Marking position that already has been marked.");
if (solutionRound[position] !=0) throw ("Marking position that was marked another round.");
int valIndex = value-1;
solution[position] = value;
int possInd = getPossibilityIndex(valIndex,position);
if (possibilities[possInd] != 0) throw ("Marking impossible position.");
// Take this value out of the possibilities for everything in the row
solutionRound[position] = round;
int rowStart = cellToRow(position)*ROW_COL_SEC_SIZE;
for (int col=0; col<ROW_COL_SEC_SIZE; col++){
int rowVal=rowStart+col;
int valPos = getPossibilityIndex(valIndex,rowVal);
//cout << "Row Start: " << rowStart << " Row Value: " << rowVal << " Value Position: " << valPos << endl;
if (possibilities[valPos] == 0){
possibilities[valPos] = round;
}
}
// Take this value out of the possibilities for everything in the column
int colStart = cellToColumn(position);
{for (int i=0; i<ROW_COL_SEC_SIZE; i++){
int colVal=colStart+(ROW_COL_SEC_SIZE*i);
int valPos = getPossibilityIndex(valIndex,colVal);
//cout << "Col Start: " << colStart << " Col Value: " << colVal << " Value Position: " << valPos << endl;
if (possibilities[valPos] == 0){
possibilities[valPos] = round;
}
}}
// Take this value out of the possibilities for everything in section
int secStart = cellToSectionStartCell(position);
{for (int i=0; i<GRID_SIZE; i++){
for (int j=0; j<GRID_SIZE; j++){
int secVal=secStart+i+(ROW_COL_SEC_SIZE*j);
int valPos = getPossibilityIndex(valIndex,secVal);
//cout << "Sec Start: " << secStart << " Sec Value: " << secVal << " Value Position: " << valPos << endl;
if (possibilities[valPos] == 0){
possibilities[valPos] = round;
}
}
}}
//This position itself is determined, it should have possibilities.
{for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0){
possibilities[valPos] = round;
}
}}
}
/**
* print the given BOARD_SIZEd array of ints
* as a sudoku puzzle. Use print options from
* member variables.
*/
void SudokuBoard::print(int* sudoku){
for(int i=0; i<BOARD_SIZE; i++){
if (printStyle == READABLE){
cout << " ";
}
if (sudoku[i]==0){
cout << '.';
} else {
cout << sudoku[i];
}
if (i == BOARD_SIZE-1){
if (printStyle == CSV){
cout << ",";
} else {
cout << endl;
}
if (printStyle == READABLE || printStyle == COMPACT){
cout << endl;
}
} else if (i%ROW_COL_SEC_SIZE==ROW_COL_SEC_SIZE-1){
if (printStyle == READABLE || printStyle == COMPACT){
cout << endl;
}
if (i%SEC_GROUP_SIZE==SEC_GROUP_SIZE-1){
if (printStyle == READABLE){
cout << "-------|-------|-------" << endl;
}
}
} else if (i%GRID_SIZE==GRID_SIZE-1){
if (printStyle == READABLE){
cout << " |";
}
}
}
}
/**
* Print the sudoku puzzle.
*/
void SudokuBoard::printPuzzle(){
print(puzzle);
}
/**
* Print the sudoku solution.
*/
void SudokuBoard::printSolution(){
print(solution);
}
SudokuBoard::~SudokuBoard(){
clearPuzzle();
delete[] puzzle;
delete[] solution;
delete[] possibilities;
delete[] solutionRound;
delete[] randomBoardArray;
delete[] randomPossibilityArray;
delete solveHistory;
delete solveInstructions;
}
LogItem::LogItem(int r, LogType t){
init(r,t,0,-1);
}
LogItem::LogItem(int r, LogType t, int v, int p){
init(r,t,v,p);
}
void LogItem::init(int r, LogType t, int v, int p){
round = r;
type = t;
value = v;
position = p;
}
LogItem::~LogItem(){
}
int LogItem::getRound(){
return round;
}
/**
* Get the type of this log item.
*/
LogItem::LogType LogItem::getType(){
return type;
}
/**
* Print the current log item. The message used is
* determined by the type of log item.
*/
void LogItem::print(){
cout << "Round: " << getRound() << " - ";
switch(type){
case GIVEN:{
cout << "Mark given";
} break;
case ROLLBACK:{
cout << "Roll back round";
} break;
case GUESS:{
cout << "Mark guess (start round)";
} break;
case HIDDEN_SINGLE_ROW:{
cout << "Mark single possibility for value in row";
} break;
case HIDDEN_SINGLE_COLUMN:{
cout << "Mark single possibility for value in column";
} break;
case HIDDEN_SINGLE_SECTION:{
cout << "Mark single possibility for value in section";
} break;
case SINGLE:{
cout << "Mark only possibility for cell";
} break;
case NAKED_PAIR_ROW:{
cout << "Remove possibilities for naked pair in row";
} break;
case NAKED_PAIR_COLUMN:{
cout << "Remove possibilities for naked pair in column";
} break;
case NAKED_PAIR_SECTION:{
cout << "Remove possibilities for naked pair in section";
} break;
case POINTING_PAIR_TRIPLE_ROW: {
cout << "Remove possibilities for row because all values are in one section";
} break;
case POINTING_PAIR_TRIPLE_COLUMN: {
cout << "Remove possibilities for column because all values are in one section";
} break;
case ROW_BOX: {
cout << "Remove possibilities for section because all values are in one row";
} break;
case COLUMN_BOX: {
cout << "Remove possibilities for section because all values are in one column";
} break;
case HIDDEN_PAIR_ROW: {
cout << "Remove possibilities from hidden pair in row";
} break;
case HIDDEN_PAIR_COLUMN: {
cout << "Remove possibilities from hidden pair in column";
} break;
case HIDDEN_PAIR_SECTION: {
cout << "Remove possibilities from hidden pair in section";
} break;
default:{
cout << "!!! Performed unknown optimization !!!";
} break;
}
if (value > 0 || position > -1){
cout << " (";
bool printed = false;
if (position > -1){
if (printed) cout << " - ";
cout << "Row: " << cellToRow(position)+1 << " - Column: " << cellToColumn(position)+1;
printed = true;
}
if (value > 0){
if (printed) cout << " - ";
cout << "Value: " << value;
printed = true;
}
cout << ")";
}
}
/**
* Given a vector of LogItems, determine how many
* log items in the vector are of the specified type.
*/
int getLogCount(vector<LogItem*>* v, LogItem::LogType type){
unsigned int count = 0;
{for (unsigned int i=0; i<v->size(); i++){
if(v->at(i)->getType() == type) count++;
}}
return count;
}
/**
* Shuffle the values in an array of integers.
*/
void shuffleArray(int* array, int size){
{for (int i=0; i<size; i++){
int tailSize = size-i;
int randTailPos = rand()%tailSize+i;
int temp = array[i];
array[i] = array[randTailPos];
array[randTailPos] = temp;
}}
}
SudokuBoard::Symmetry getRandomSymmetry(){
switch (rand()%4){
case 0: return SudokuBoard::ROTATE90;
case 1: return SudokuBoard::ROTATE180;
case 2: return SudokuBoard::MIRROR;
case 3: return SudokuBoard::FLIP;
}
return SudokuBoard::ROTATE90; // NOTE: default action
}
/**
* Given the index of a cell (0-80) calculate
* the column (0-8) in which that cell resides.
*/
static inline int cellToColumn(int cell){
return cell%ROW_COL_SEC_SIZE;
}
/**
* Given the index of a cell (0-80) calculate
* the row (0-8) in which it resides.
*/
static inline int cellToRow(int cell){
return cell/ROW_COL_SEC_SIZE;
}
/**
* Given the index of a cell (0-80) calculate
* the section (0-8) in which it resides.
*/
static inline int cellToSection(int cell){
return (cell/SEC_GROUP_SIZE*GRID_SIZE)
+ (cellToColumn(cell)/GRID_SIZE);
}
/**
* Given the index of a cell (0-80) calculate
* the cell (0-80) that is the upper left start
* cell of that section.
*/
static inline int cellToSectionStartCell(int cell){
return (cell/SEC_GROUP_SIZE*SEC_GROUP_SIZE)
+ (cellToColumn(cell)/GRID_SIZE*GRID_SIZE);
}
/**
* Given a row (0-8) calculate the first cell (0-80)
* of that row.
*/
static inline int rowToFirstCell(int row){
return ROW_COL_SEC_SIZE*row;
}
/**
* Given a column (0-8) calculate the first cell (0-80)
* of that column.
*/
static inline int columnToFirstCell(int column){
return column;
}
/**
* Given a section (0-8) calculate the first cell (0-80)
* of that section.
*/
static inline int sectionToFirstCell(int section){
return (section%GRID_SIZE*GRID_SIZE)
+ (section/GRID_SIZE*SEC_GROUP_SIZE);
}
/**
* Given a value for a cell (0-8) and a cell (0-80)
* calculate the offset into the possibility array (0-728).
*/
static inline int getPossibilityIndex(int valueIndex, int cell){
return valueIndex+(ROW_COL_SEC_SIZE*cell);
}
/**
* Given a row (0-8) and a column (0-8) calculate the
* cell (0-80).
*/
static inline int rowColumnToCell(int row, int column){
return (row*ROW_COL_SEC_SIZE)+column;
}
/**
* Given a section (0-8) and an offset into that section (0-8)
* calculate the cell (0-80)
*/
static inline int sectionToCell(int section, int offset){
return sectionToFirstCell(section)
+ ((offset/GRID_SIZE)*ROW_COL_SEC_SIZE)
+ (offset%GRID_SIZE);
}
}