brute force recursive sudoku solver

[jakefrench]

Dear All,

Could anyone help with this Sudoku brute force recursive solver? (shown below): It gets caught in a loop I think. I've also included the algorithm outline I use (taken from wikipedia), and the input text file ('sudokuInput.txt') I'm trying is:

0 3 0 0 7 0 0 0 0
6 0 0 1 0 5 0 0 0
0 0 0 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 0
0 0 0 0 8 0 0 7 0

Best wishes,

Jake



#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;

const int n = 9, p = 9;
void printSudoku( const int sudokuBoard[n][p], bool printToFile );
void getSudoku( int sudokuBoard[n][p], int sudokuMask[n][p] );
bool violationCheck( int sudokuBoard[n][p], const int sudokuMask[n][p], int row, int col, int number );
void solveIndividualCell( int sudokuBoard[n][p], const int sudokuMask[n][p], int row, int col, int startLoopFromHere );
// is sudokuBoard[row][col] = number OK?
// Yes -> return violation(true): meaning number can't fit in location, check number+1..
// No -> return violation(false): meaning number is OK to fit in location

int main()
{
bool solvedYet = false;
int i, j;
int sudokuBoard[n][p], sudokuMask[n][p];

// Load Sudoku numbers
cout << "Data read from file:" << endl;
getSudoku( sudokuBoard, sudokuMask );
printSudoku( sudokuBoard, false );
system("pause");


// Solve puzzle
for( i=0; i<n; i++ )
{
for( j=0; j<p; j++ )
solveIndividualCell( sudokuBoard, sudokuMask, i, j, 1 );
}


// Print results
cout << endl << endl;
cout << "** Print Solution **" << endl;
printSudoku( sudokuBoard, true );
system("pause");
return 0;
}



void getSudoku( int sudokuBoard[n][p], int sudokuMask[n][p] )
{
char inputName[] = "sudokuInput.txt";
// char inputName[] = "sudokuInput_easy.txt";
ifstream inFile;
inFile.open( inputName );
if( inFile.is_open() == false )
{
cout << "\aSorry, unable to find the input file(" << inputName << ")" << endl;
system("pause");
exit(1);
}
else // Get the numbers
{
for( int i=0; i<n; i++ )
{
for( int j=0; j<p; j++ )
{
inFile >> sudokuBoard[i][j];
if( sudokuBoard[i][j] == 0 )
sudokuMask[i][j] = true;
else
sudokuMask[i][j] = false;
}
}
inFile.close();
}
}




void printSudoku( const int sudokuBoard[n][p], bool printToFile )
{
if( printToFile == false )
{
for( int i=0; i<n; i++ )
{
if( (i%3 == 0) && (i>0) )
cout << setw(2) << "------------------------------" << endl;
for( int j=0; j<p; j++ )
{
if( (j%3 == 0) && (j>0) )
cout << setw(2) << "|";
cout << setw(2) << sudokuBoard[i][j] << " ";
}
cout << endl;
}
}
else
{
ofstream outFile;
outFile.open( "sudokuSolution.txt" );
for( int i=0; i<n; i++ )
{
if( (i%3 == 0) && (i>0) )
outFile << setw(2) << "------------------------------" << endl;
for( int j=0; j<p; j++ )
{
if( (j%3 == 0) && (j>0) )
outFile << setw(2) << "|";
outFile << setw(2) << sudokuBoard[i][j] << " ";
}
outFile << endl;
}
outFile.close();
printSudoku( sudokuBoard, false );
}
}

// bool violationCheck( ..)
// is number violation?
// Yes -> return violation(true)
// No -> return violation(false)
bool violationCheck( int sudokuBoard[n][p], const int sudokuMask[n][p], int row, int col, int number )
{
int i, j;
cout << "sudokuBoard[" << row << "][" << col << "] = " << sudokuBoard[row][col];
cout << " - try[" << number << "]: ";

// cell check - test, sudokuBoard[row][col] !=0 ?
if( sudokuMask[row][col] == 0 )
{
cout << "Already occupied.." << endl;
return false;
}


// row and cell check -
for( i=0; i<n; i++ )
{
if( sudokuBoard[row][i] == number )
{ cout << "fail.." << endl; return true; }
else if( sudokuBoard[i][col] == number )
{ cout << "fail.." << endl; return true; }
}


// Box check - can number fit into 3x3 grid
int iStart, jStart;
if( row < 3 )
iStart = 0;
else if( (row>=3) && (row<6) )
iStart = 3;
else
iStart = 6;
// now col's
if( col < 3 )
jStart = 0;
else if( (col>=3) && (col<6) )
jStart = 3;
else
jStart = 6;


for( i=iStart; i<(iStart+3); i++ )
{
for( j=jStart; j<(jStart+3); j++ )
{
if( sudokuBoard[i][j] == number )
{ cout << "fail.." << endl; return true; }
}
}
sudokuBoard[row][col] = number;
cout << "success!" << endl << endl;
return false;
}






/* When checking for violations, it is discovered that the "1" is not allowed,
so the value is advanced to a "2".. If a cell is discovered where none of the 9 digits is allowed,
then the algorithm leaves that cell blank and moves back to the previous cell.
The value in that cell is then incremented by one.
*/

void solveIndividualCell(int sudokuBoard[n][p], const int sudokuMask[n][p], int row, int col, int startLoopFromHere )
{
bool violation = false;
bool cellSuccess = false;
int violationCounter = 0;
int maxAllowedViolations = 10 - startLoopFromHere;

for(int test=startLoopFromHere; test<10; test++)
{
violation = violationCheck( sudokuBoard, sudokuMask, row, col, test );
if( violation == true )
violationCounter++;
else
{ // reset counter
violationCounter = 0;
break;
}
}


// at this point we know that numbers 1-9 dont fit into sudokuBoard[row][col]
// we now have to find the last place number placed on the board and adjust it:
if( violationCounter == maxAllowedViolations )
{
int tempRow, tempCol, tryValue;
cout << endl << endl;
cout << "** Backtrack Required for cell[" << row << "][" << col << "] **" << endl;
printSudoku( sudokuBoard, false);
cout << "Search for previous (suitable) cell:" << endl;



for( tempRow=row; tempRow>=0; tempRow--)
{
for( tempCol=col; tempCol>=0; tempCol--)
{
cout << "sudokuBoard[" << tempRow << "][" << tempCol << "] = ";
cout << sudokuBoard[tempRow][tempCol];

if( sudokuMask[tempRow][tempCol]==0 )
cout << " not suitable" << endl;
else if( tempRow==row && tempCol==col )
{
cout << " not suitable" << endl;
sudokuBoard[tempRow][tempCol] = 0;
}
else
{
cout << " suitable, test new values in this cell.." << endl;
tryValue = sudokuBoard[tempRow][tempCol] + 1;
solveIndividualCell( sudokuBoard, sudokuMask, tempRow, tempCol, tryValue);
cout << "Recursive Backtrack Successfull, return to cell[" << row << "][" << col << "]:" << endl;
solveIndividualCell( sudokuBoard, sudokuMask, row, col, 1);
system("pause");
return;
}
}
}
}
}