Sudoku Solver (enhanced Latin square)
A. First Edition
This is only an enhanced Latin square search and it is assignment from comb. algo.
Sudoku Solver
In the Sudoku puzzle, you are given a partially filled latin square of order
9. The
9 〜 9 matrix is further subdivided into nine 3 〜 3 submatrices. The
objective is to
complete it to a latin square, with the additional constraint that each of
the nine
submatrices also contains only the numbers from 1 to 9. For more information
on
Sudoku, please consult a local newspaper or visit the many web sites on this
subject,
e.g. http://en.wikipedia.org/wiki/Sudoku.
Write a backtrack program that solves the Sudoku puzzle. The input will be a
9 〜 9
matrix, where the unknowns are represented by a 0(zero). You should print
out a
solution, if it exists, and also the the number of solutions. Normally, a
Sudoku puzzle
has a unique solution. However, for our exercise, some input may have no
solutions,
and others may have more than one solutions.
Is there anything special for this program? I cannot see.
It is a trivial backtrack or depth-first-search or deterministic-finite-automaton etc.
I think it is a trivial program because this kind of DFS or DFA program has a kind of pattern or template which I have even written one a
couple of years ago.
Or you may want to know some details about Latin square.
E.Further improvement
F.File listing
1. main.cpp (main)
file name: main.cpp
#include <iostream> #include <fstream> using namespace std; const size_t SquareSize=9; typedef size_t Vector[SquareSize]; typedef Vector Square[SquareSize]; //size_t primeMap[SquareSize+1]={1, 2, 3, 5, 7, 11,13, 17, 23, 29}; //const size_t Checker=2*3*5*7*11*13*17*23*29; Square square; Square original; size_t counter=0; void readFromFile(char* fileName); void doFilling(size_t row, size_t col); void printSquare(); bool checkRowCol(size_t row, size_t col); int main() { size_t row=0, col=0; readFromFile("data3.txt"); counter=0; printSquare(); doFilling(row, col); return 0; } void printSquare() { size_t row, col; for (row=0; row<SquareSize; row++) { for (col=0; col<SquareSize; col++) { cout<<square[row][col]<<","; } cout<<"\n"; } } void readFromFile(char* fileName) { ifstream in(fileName); for (int i=0; i<SquareSize; i++) { for (int j=0; j<SquareSize; j++) { in>>square[i][j]; original[i][j]=square[i][j];//make an old copy } } } void doFilling(size_t row, size_t col) { //cout<<"row="<<row<<" col="<<col<<"\n"; //printSquare(); if (row==SquareSize) { counter++; cout<<"this is "<<counter<<"th solution\n"; printSquare(); return; } if (original[row][col]!=0) { if (col<SquareSize-1) { doFilling(row, col+1); } else { doFilling(row+1, 0); } } else { //oldValue= square[row][col]; for (size_t choice=1; choice<=SquareSize; choice++) { square[row][col]=choice; if (checkRowCol(row, col)) { if (col<SquareSize-1) { doFilling(row, col+1); } else { doFilling(row+1, 0); } } } //restore square[row][col]=0; } } bool checkRowCol(size_t row, size_t col) { bool rowFlag[SquareSize], colFlag[SquareSize]; size_t i, j; size_t subRowOffset=(row/3)*3; size_t subColOffset=(col/3)*3; for (i=0; i<3; i++) { for (j=0; j<3; j++) { if (row!=i+subRowOffset||col!=j+subColOffset) { if (square[row][col]==square[i+subRowOffset][j+subColOffset]) { return false; } } } } for (i=0; i<SquareSize; i++) { rowFlag[i]=true; colFlag[i]=true; } for (i=0; i<SquareSize; i++) { //no repeat number if (square[row][i]!=0) { if (rowFlag[square[row][i]-1]) { rowFlag[square[row][i]-1]=false; } else { return false; } } if (square[i][col]!=0) { if (colFlag[square[i][col]-1]) { colFlag[square[i][col]-1]=false; } else { return false; } } } return true; }
The result is like following:
data1.txt
2 0 4 0 0 7 0 0 5 0 0 0 0 0 0 0 0 7 0 5 0 1 0 0 0 9 2 5 0 2 0 7 3 0 1 0 0 0 0 0 0 0 0 0 0 0 3 0 6 8 0 7 0 4 8 6 0 0 0 4 0 2 0 3 0 0 0 0 0 0 0 0 4 0 0 2 0 0 8 0 1
result:
2,0,4,0,0,7,0,0,5, 0,0,0,0,0,0,0,0,7, 0,5,0,1,0,0,0,9,2, 5,0,2,0,7,3,0,1,0, 0,0,0,0,0,0,0,0,0, 0,3,0,6,8,0,7,0,4, 8,6,0,0,0,4,0,2,0, 3,0,0,0,0,0,0,0,0, 4,0,0,2,0,0,8,0,1, now begin searching solutions: this is 1th solution 2,8,4,3,9,7,1,6,5, 9,1,6,4,2,5,3,8,7, 7,5,3,1,6,8,4,9,2, 5,4,2,9,7,3,6,1,8, 6,7,8,5,4,1,2,3,9, 1,3,9,6,8,2,7,5,4, 8,6,1,7,5,4,9,2,3, 3,2,7,8,1,9,5,4,6, 4,9,5,2,3,6,8,7,1, Press any key to continue
data2.txt
2 0 4 0 0 7 0 0 5 0 0 0 0 0 0 0 0 7 0 5 0 1 0 0 0 9 2 5 0 2 0 0 3 0 1 0 0 0 0 0 0 0 0 0 0 0 3 0 6 8 0 7 0 4 8 6 0 0 0 4 0 2 0 3 0 0 0 0 0 0 0 0 4 0 0 2 0 0 8 0 1
result:
2,0,4,0,0,7,0,0,5,
0,0,0,0,0,0,0,0,7,
0,5,0,1,0,0,0,9,2,
5,0,2,0,0,3,0,1,0,
0,0,0,0,0,0,0,0,0,
0,3,0,6,8,0,7,0,4,
8,6,0,0,0,4,0,2,0,
3,0,0,0,0,0,0,0,0,
4,0,0,2,0,0,8,0,1,
now begin searching solutions:
this is 1th solution
2,8,4,3,9,7,1,6,5,
9,1,6,4,2,5,3,8,7,
7,5,3,1,6,8,4,9,2,
5,4,2,9,7,3,6,1,8,
6,7,8,5,4,1,2,3,9,
1,3,9,6,8,2,7,5,4,
8,6,1,7,5,4,9,2,3,
3,2,7,8,1,9,5,4,6,
4,9,5,2,3,6,8,7,1,
this is 2th solution
2,8,4,3,9,7,1,6,5,
9,1,6,4,2,5,3,8,7,
7,5,3,1,6,8,4,9,2,
5,7,2,9,4,3,6,1,8,
6,4,8,5,7,1,2,3,9,
1,3,9,6,8,2,7,5,4,
8,6,1,7,5,4,9,2,3,
3,2,7,8,1,9,5,4,6,
4,9,5,2,3,6,8,7,1,
this is 3th solution
2,8,4,3,9,7,1,6,5,
9,1,6,4,2,5,3,8,7,
7,5,3,1,6,8,4,9,2,
5,7,2,9,4,3,6,1,8,
6,4,8,7,5,1,2,3,9,
1,3,9,6,8,2,7,5,4,
8,6,1,5,7,4,9,2,3,
3,2,7,8,1,9,5,4,6,
4,9,5,2,3,6,8,7,1,
this is 4th solution
2,8,4,3,9,7,1,6,5,
9,1,6,4,2,5,3,8,7,
7,5,3,1,6,8,4,9,2,
5,7,2,9,4,3,6,1,8,
6,4,8,7,5,1,2,3,9,
1,3,9,6,8,2,7,5,4,
8,6,7,5,1,4,9,2,3,
3,2,1,8,7,9,5,4,6,
4,9,5,2,3,6,8,7,1,
Press any key to continue
data3.txt
1 0 0 0 6 0 0 0 8 0 2 0 3 0 0 0 7 0 0 0 3 0 0 1 6 0 0 0 0 0 4 0 9 0 2 0 3 0 0 0 5 0 0 0 6 0 8 0 1 0 6 0 0 0 0 0 2 8 0 0 7 0 0 0 3 1 0 0 0 0 8 0 4 0 0 0 2 0 3 0 9
result:
1,5,7,9,6,2,4,3,8, 8,2,6,3,4,5,9,7,1, 9,4,3,7,8,1,6,5,2, 6,1,5,4,3,9,8,2,7, 3,7,9,2,5,8,1,4,6, 2,8,4,1,7,6,5,9,3, 5,9,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 24th solution 1,5,7,9,6,2,4,3,8, 8,2,6,3,4,5,9,7,1, 9,4,3,7,8,1,6,5,2, 6,1,5,4,7,9,8,2,3, 3,7,4,2,5,8,1,9,6, 2,8,9,1,3,6,5,4,7, 5,9,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 25th solution 1,5,7,9,6,2,4,3,8, 8,2,6,3,4,5,9,7,1, 9,4,3,7,8,1,6,5,2, 6,1,5,4,7,9,8,2,3, 3,7,9,2,5,8,1,4,6, 2,8,4,1,3,6,5,9,7, 5,9,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 26th solution 1,5,7,9,6,2,4,3,8, 9,2,6,3,4,8,5,7,1, 8,4,3,5,7,1,6,9,2, 6,7,5,4,8,9,1,2,3, 3,1,9,2,5,7,8,4,6, 2,8,4,1,3,6,9,5,7, 5,9,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,7,2,5,3,1,9, this is 27th solution 1,5,7,9,6,2,4,3,8, 9,2,6,3,4,8,5,7,1, 8,4,3,5,7,1,6,9,2, 7,6,5,4,8,9,1,2,3, 3,1,9,2,5,7,8,4,6, 2,8,4,1,3,6,9,5,7, 5,9,2,8,1,3,7,6,4, 6,3,1,7,9,4,2,8,5, 4,7,8,6,2,5,3,1,9, this is 28th solution 1,7,4,9,6,2,5,3,8, 8,2,6,3,4,5,9,7,1, 5,9,3,7,8,1,6,4,2, 6,1,5,4,3,9,8,2,7, 3,4,7,2,5,8,1,9,6, 2,8,9,1,7,6,4,5,3, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 29th solution 1,7,4,9,6,2,5,3,8, 8,2,6,3,4,5,9,7,1, 5,9,3,7,8,1,6,4,2, 6,1,5,4,7,9,8,2,3, 3,4,7,2,5,8,1,9,6, 2,8,9,1,3,6,4,5,7, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 30th solution 1,7,4,9,6,2,5,3,8, 8,2,6,3,4,5,9,7,1, 9,5,3,7,8,1,6,4,2, 6,1,5,4,3,9,8,2,7, 3,4,7,2,5,8,1,9,6, 2,8,9,1,7,6,4,5,3, 5,9,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 31th solution 1,7,4,9,6,2,5,3,8, 8,2,6,3,4,5,9,7,1, 9,5,3,7,8,1,6,4,2, 6,1,5,4,7,9,8,2,3, 3,4,7,2,5,8,1,9,6, 2,8,9,1,3,6,4,5,7, 5,9,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 32th solution 1,7,5,9,6,2,4,3,8, 6,2,4,3,8,5,9,7,1, 8,9,3,7,4,1,6,5,2, 5,1,6,4,3,9,8,2,7, 3,4,7,2,5,8,1,9,6, 2,8,9,1,7,6,5,4,3, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 33th solution 1,7,5,9,6,2,4,3,8, 6,2,4,3,8,5,9,7,1, 8,9,3,7,4,1,6,5,2, 5,1,6,4,7,9,8,2,3, 3,4,7,2,5,8,1,9,6, 2,8,9,1,3,6,5,4,7, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 34th solution 1,7,5,9,6,2,4,3,8, 9,2,6,3,4,8,5,7,1, 8,4,3,5,7,1,6,9,2, 6,5,7,4,8,9,1,2,3, 3,1,9,2,5,7,8,4,6, 2,8,4,1,3,6,9,5,7, 5,9,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,7,2,5,3,1,9, this is 35th solution 1,9,4,7,6,2,5,3,8, 8,2,6,3,4,5,9,7,1, 5,7,3,9,8,1,6,4,2, 6,1,5,4,3,9,8,2,7, 3,4,7,2,5,8,1,9,6, 2,8,9,1,7,6,4,5,3, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 36th solution 1,9,4,7,6,2,5,3,8, 8,2,6,3,4,5,9,7,1, 5,7,3,9,8,1,6,4,2, 6,1,5,4,7,9,8,2,3, 3,4,7,2,5,8,1,9,6, 2,8,9,1,3,6,4,5,7, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 37th solution 1,9,5,7,6,2,4,3,8, 6,2,4,3,8,5,9,7,1, 8,7,3,9,4,1,6,5,2, 5,1,6,4,3,9,8,2,7, 3,4,7,2,5,8,1,9,6, 2,8,9,1,7,6,5,4,3, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 38th solution 1,9,5,7,6,2,4,3,8, 6,2,4,3,8,5,9,7,1, 8,7,3,9,4,1,6,5,2, 5,1,6,4,7,9,8,2,3, 3,4,7,2,5,8,1,9,6, 2,8,9,1,3,6,5,4,7, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 39th solution 1,9,7,2,6,4,5,3,8, 5,2,6,3,9,8,4,7,1, 8,4,3,5,7,1,6,9,2, 7,6,5,4,8,9,1,2,3, 3,1,9,7,5,2,8,4,6, 2,8,4,1,3,6,9,5,7, 9,5,2,8,1,3,7,6,4, 6,3,1,9,4,7,2,8,5, 4,7,8,6,2,5,3,1,9, this is 40th solution 1,9,7,2,6,5,4,3,8, 5,2,6,3,4,8,9,7,1, 8,4,3,9,7,1,6,5,2, 6,7,5,4,8,9,1,2,3, 3,1,4,7,5,2,8,9,6, 2,8,9,1,3,6,5,4,7, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 41th solution 1,9,7,2,6,5,4,3,8, 5,2,6,3,4,8,9,7,1, 8,4,3,9,7,1,6,5,2, 6,7,5,4,8,9,1,2,3, 3,1,9,7,5,2,8,4,6, 2,8,4,1,3,6,5,9,7, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 42th solution 1,9,7,2,6,5,4,3,8, 6,2,5,3,4,8,9,7,1, 8,4,3,9,7,1,6,5,2, 5,7,6,4,8,9,1,2,3, 3,1,4,7,5,2,8,9,6, 2,8,9,1,3,6,5,4,7, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 43th solution 1,9,7,2,6,5,4,3,8, 6,2,5,3,4,8,9,7,1, 8,4,3,9,7,1,6,5,2, 5,7,6,4,8,9,1,2,3, 3,1,9,7,5,2,8,4,6, 2,8,4,1,3,6,5,9,7, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,5,2,7,3,1,9, this is 44th solution 1,9,7,5,6,2,4,3,8, 5,2,6,3,4,8,9,7,1, 8,4,3,7,9,1,6,5,2, 7,6,5,4,8,9,1,2,3, 3,1,4,2,5,7,8,9,6, 2,8,9,1,3,6,5,4,7, 9,5,2,8,1,3,7,6,4, 6,3,1,9,7,4,2,8,5, 4,7,8,6,2,5,3,1,9, this is 45th solution 1,9,7,5,6,2,4,3,8, 5,2,6,3,4,8,9,7,1, 8,4,3,7,9,1,6,5,2, 7,6,5,4,8,9,1,2,3, 3,1,9,2,5,7,8,4,6, 2,8,4,1,3,6,5,9,7, 9,5,2,8,1,3,7,6,4, 6,3,1,9,7,4,2,8,5, 4,7,8,6,2,5,3,1,9, this is 46th solution 1,9,7,5,6,2,4,3,8, 5,2,6,3,4,8,9,7,1, 8,4,3,9,7,1,6,5,2, 6,7,5,4,8,9,1,2,3, 3,1,4,2,5,7,8,9,6, 2,8,9,1,3,6,5,4,7, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,7,2,5,3,1,9, this is 47th solution 1,9,7,5,6,2,4,3,8, 5,2,6,3,4,8,9,7,1, 8,4,3,9,7,1,6,5,2, 6,7,5,4,8,9,1,2,3, 3,1,9,2,5,7,8,4,6, 2,8,4,1,3,6,5,9,7, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,7,2,5,3,1,9, this is 48th solution 1,9,7,5,6,2,4,3,8, 5,2,6,3,4,8,9,7,1, 8,4,3,9,7,1,6,5,2, 7,6,5,4,8,9,1,2,3, 3,1,4,2,5,7,8,9,6, 2,8,9,1,3,6,5,4,7, 9,5,2,8,1,3,7,6,4, 6,3,1,7,9,4,2,8,5, 4,7,8,6,2,5,3,1,9, this is 49th solution 1,9,7,5,6,2,4,3,8, 5,2,6,3,4,8,9,7,1, 8,4,3,9,7,1,6,5,2, 7,6,5,4,8,9,1,2,3, 3,1,9,2,5,7,8,4,6, 2,8,4,1,3,6,5,9,7, 9,5,2,8,1,3,7,6,4, 6,3,1,7,9,4,2,8,5, 4,7,8,6,2,5,3,1,9, this is 50th solution 1,9,7,5,6,2,4,3,8, 6,2,5,3,4,8,9,7,1, 8,4,3,9,7,1,6,5,2, 5,7,6,4,8,9,1,2,3, 3,1,4,2,5,7,8,9,6, 2,8,9,1,3,6,5,4,7, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,7,2,5,3,1,9, this is 51th solution 1,9,7,5,6,2,4,3,8, 6,2,5,3,4,8,9,7,1, 8,4,3,9,7,1,6,5,2, 5,7,6,4,8,9,1,2,3, 3,1,9,2,5,7,8,4,6, 2,8,4,1,3,6,5,9,7, 9,5,2,8,1,3,7,6,4, 7,3,1,6,9,4,2,8,5, 4,6,8,7,2,5,3,1,9, this is 52th solution 1,9,7,5,6,4,2,3,8, 5,2,6,3,9,8,4,7,1, 8,4,3,2,7,1,6,9,5, 7,6,5,4,8,9,1,2,3, 3,1,9,7,5,2,8,4,6, 2,8,4,1,3,6,9,5,7, 9,5,2,8,1,3,7,6,4, 6,3,1,9,4,7,5,8,2, 4,7,8,6,2,5,3,1,9, Press any key to continue
data4.txt
2 0 4 0 0 7 0 0 5 0 0 0 0 0 0 0 0 7 0 5 0 1 0 0 0 9 2 5 0 2 0 7 3 0 1 0 0 0 0 0 0 0 0 0 0 0 3 0 6 8 0 7 0 4 8 6 0 0 0 4 0 2 0 3 0 0 0 9 0 0 0 0 4 0 0 2 0 0 8 0 1
result:
2,0,4,0,0,7,0,0,5, 0,0,0,0,0,0,0,0,7, 0,5,0,1,0,0,0,9,2, 5,0,2,0,7,3,0,1,0, 0,0,0,0,0,0,0,0,0, 0,3,0,6,8,0,7,0,4, 8,6,0,0,0,4,0,2,0, 3,0,0,0,9,0,0,0,0, 4,0,0,2,0,0,8,0,1, now begin searching solutions: Press any key to continue
data5.txt
0 2 0 0 0 8 1 0 0 0 3 0 0 5 0 7 0 0 0 0 8 0 3 0 0 0 4 0 0 0 8 0 0 5 0 0 8 7 0 0 0 0 0 9 3 0 0 6 0 0 9 0 0 0 6 0 0 0 1 0 2 0 0 0 0 3 0 9 0 0 1 0 0 0 9 2 0 0 0 7 0
result:
0,2,0,0,0,8,1,0,0, 0,3,0,0,5,0,7,0,0, 0,0,8,0,3,0,0,0,4, 0,0,0,8,0,0,5,0,0, 8,7,0,0,0,0,0,9,3, 0,0,6,0,0,9,0,0,0, 6,0,0,0,1,0,2,0,0, 0,0,3,0,9,0,0,1,0, 0,0,9,2,0,0,0,7,0, now begin searching solutions: this is 1th solution 7,2,5,9,4,8,1,3,6, 9,3,4,6,5,1,7,8,2, 1,6,8,7,3,2,9,5,4, 3,9,1,8,2,4,5,6,7, 8,7,2,1,6,5,4,9,3, 5,4,6,3,7,9,8,2,1, 6,8,7,5,1,3,2,4,9, 2,5,3,4,9,7,6,1,8, 4,1,9,2,8,6,3,7,5, Press any key to continue