Latin Square

         Sudoku Solver (enhanced Latin square)

A. First Edition
This is only an enhanced Latin square search and it is assignment from comb. algo.
B.The problem

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.

　

C.The idea of program
　
Is there anything special for this program? I cannot see.
It is a trivial backtrack or depth-first-search or deterministic-finite-automaton etc.
　
D.The major functions
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



			



				 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)