combinatorial algorithm programs

1. (5 marks) An efficient Iterator for sets
Section 1.7.1 of the textbook gives the bit array data structure for sets. However, it
does not have an efficient way of looping through all the elements of a set. In this
question, we try to add a few routines which allows one to iterate over the elements of
a set efficiently.
(a) (1 marks) Similar to the array look on page 21 of the textbook, we want to define
an array leftmost where leftmost[i] gives the bit number of the leftmost bit in
the binary representation of the index i. For example, leftmost[9] is 3 because
9 is 1001 in binary, and we are using the convention that the rightmost bit is bit
0.
What are the entries in leftmost[0] to leftmost[15]?
(b) (2 marks) How would you initialize a 16-bit table leftmost[0] to leftmost[65535]?
Explain you answer in the form of a pseudocode.
(c) (2 marks) Give the pseudocode for a next(A,x) routine which returns the smallest
element of A which is greater than x. If no such element exists, return −1. The
context for this routine is the same as those of Section 1.7.1, i.e., the ground set
is {0, . . . , n}, the word size is , etc.
2. (2 marks) Integer Partition
How would you generate all the partitions of an even integer n with the added restriction
that all its parts must be even?
3. (4 marks) Unranking of subsets based on ordering defined in Ex. 2.10
In Exercise 2.10 on page 64 of the textbook, the subsets of an n-element set is ordered
first in increasing size, and then in lexicographical order. What is the 2,000,000th
1
subset of S = {1, . . . , 30} in this ordering. Give a brief explanation how you arrive
at the answer. A brute-force method of writing a program to generate all the subsets
and then printing out the 2,000,000th subset will give you only half the marks.
4. (4 marks) MaxClique and Sampling Bound
Consider the maximum clique problem as specified by Ex. 4.9 (p. 147) of your textbook,
which is based on using Algorithm 4.19: MAXCLIQUE2(`) (p. 139) of the
textbook. Assume that your input data is the graph given in part (b) of Ex. 4.9
and consider the particular instance when MAXCLIQUE2 is called with ` = 1 and
[x0] = [8]. Assume also that SAMPLINGBOUND (Algorithm 4.17, p. 138) is used as
the bounding function.
What value is returned by SAMPLINGBOUND? You should treat this as a penciland-
paper question, rather than just running the program and printing out the answer.
You have to show in your answer that you understand what is going on.
Please note that Exercise 4.9 has a minor typo. The set V should be expanded to
include also vertices e and f.
5. (15 marks) Estimating the number of Sudoku grids with no repeats in the
diagonals
Since the number of Sudoku grids is known (see http://en.wikipedia.org/wiki/Sudoku),
in this question, we will be estimating the number of Sudoku grids with the extra
property that the two diagonals are also permutations of the numbers 1 to 9. These
two diagonals are the main diagonal, running from top left to the bottom right of the
Sudoku grid, and the back diagonal, running from the top right to the bottom left.
For example, the input file “test 3” for assignment 5 has the two diagonals filled in.
The main diagonal, reading from top left to bottom right, is [1,2,3,4,5,6,7,8,9], and the
back diagonal, reading from top right to bottom left, is [8,7,6,9,5,1,2,3,4]. Both of this
diagonals are permutations of 1 to 9.
You will be asked to submit the source codes of your program with your answers.
In order to help me compile and test run your programs, please specify whether you
have developed them on a Windows platform, or a Linux platform. Also, I prefer
separate programs for each of the parts. However, if you develop one program that
solves multiple parts, please give clear instructions on how to run your program to get
the desired output.
(a) (3 marks)
Modify your backtrack program from Assignment 5 so that it will find Sudoku
grids with this added restriction. Test your program with the input files “test 2”,
and “test 3” from Assignment 5. Your program should print out the following:
i. the first solution, if any,
ii. the total number of solutions, and
iii. the size of the backtrack search tree.
2
Besides the first solution, printing of other solutions are optional.
The size of the backtrack search tree is the number of nodes in the tree.
Please submit a copy of the source codes of the program that solves this part
with your answers.
Note: if you want to start with my version of the Sudoku solver instead of your
own, please email me.
(b) (5 marks)
It is difficult to estimate the number of solutions if the backtrack program runs
into a lot of dead ends. The objective of this part is to modify your solution to
part (a) so that it is “better” at finding solutions. The idea is to backtrack on the
cell with the least number of viable possibilities. If, at any time in the backtrack
process, a cell has no viable choice, the grid cannot be completed. If there is
only one choice, the choice is forced. In general, we choose a cell with the least
number of possibilities. In order to make your results comparable to mine, let us
adopt the tie-breaking procedure that amongst the cells with the same number
of viable choices, we take the one that comes first in the row major order. In
other words, amongst those cells with the same number of viable possibilities, we
backtrack on the cell with the smallest row number, and amongst those with the
same row number, the one with the smallest column number.
Modify your program from part (a) so that at every level, it backtracks on the
cell with the least number of viable possibilities. As in part (a), your program
should print out the following:
i. the first solution, if any,
ii. the total number of solutions, and
iii. the size of the search tree.
Again, the printing of solutions, except the first one, is optional.
Please submit a copy of the source codes of the program that solves this part
with your answers.
(c) (7 marks)
Now, modify your solution to part (b) to estimate the number of Sudoku grid
with the added restriction that both diagonals are also permutations of 1 to 9.
Your program should still be able to accept a partially filled Sudoku grid, and
perform the estimation. Your program should provide the following output:
i. the number of estimation runs,
ii. the estimated size of the backtrack search tree at each level,
iii. the total estimated size of the backtrack search tree,
iv. the estimated number of solutions, and
v. the number of solutions the program happened to generate while doing estimations.
Please do not make too many estimation runs; 100 runs is probably sufficient.
3
Please run your program with the input file “test 3”, and also with an input file
where all the entries are 0’s. The latter corresponds to a blank initial grid, and
its estimated number of solutions is the estimate number of Sudoku grids where
both diagonals are also permutations.
If you cannot get a working program for part (b), you can do estimation by modifying
the program from part (a). However, there will be a penalty of 2 marks for
taking this alternative. Besides, you will have a difficult time getting reasonable
estimates of the number of Sudoku grids with no repeats in the diagonals.
Please submit your source code with your answers.

The following is a series of programs and its running result.

file name: question1

a) If we assume binary 0000 has no left-most bit at all, then left(0)= -1 or undefined. 
decimal	binary	left()
0	0000	-1
1	0001	0
2	0010	1
3	0011	1
4	0100	2
5	0101	2
6	0110	2
7	0111	2
8	1000	3
9	1001	3
10	1010	3
11	1011	3
12	1100	3
13	1101	3
14	1110	3
15	1111	3
  
b)	short array[65536];
short e=01;
for (short i=0; i<65536; i++)
{
	if (i>= pow(2, e))
	{
		e++;
	}
	array[i]=e-1;
}

file name: question2

#include <iostream>

using namespace std;

const int MaxNumber=20;

int array[MaxNumber];


void displayArray(int* array, int size)
{
	cout<<"[";
	for (int i=0; i<size; i++)
	{
		cout<<array[i];
		if (i!=size-1)
		{
			cout<<",";
		}
	}
	cout<<"]\n";
}

//here we 
void recEvenPart(int m, int B, int N)
{
	if (m==0)
	{
		displayArray(array, N);
	}
	else
	{
		int size=B<m?B:m;
		for (int i=2; i<=size; i+=2)
		{
			array[N]=i;
			recEvenPart(m-i, i, N+1);
		}
	}
}

void evenGenPart(int m)
{
	recEvenPart(m,m, 0);
}



int main()
{
	evenGenPart(12);


	return 0;
}

//the following is the running result when input m=12
[2,2,2,2,2,2]
[4,2,2,2,2]
[4,4,2,2]
[4,4,4]
[6,2,2,2]
[6,4,2]
[6,6]
[8,2,2]
[8,4]
[10,2]
[12]
Press any key to continue

file name: question3

#include <iostream>

using namespace std;

const int MaxArraySize=32;

int array[MaxArraySize];

int combineNumber(int n, int k)
{
	int result =1;
	for (int i=0; i<k; i++)
	{
		result=result*(n-i)/(i+1);
	}

	return result;
}



//assume array contains k elements, index starts from 0
int lexRank(int n, int k, int* array)
{
	int result=0, i, j;
	for (i=0; i<k; i++)
	{	
		if (i==0)
		{
			for (j=1; j<array[0]; j++)
			{
				result+=combineNumber(n-j, k-i-1);
			}
		}
		else
		{
			if (array[i-1]+1<=array[i]-1)
			{
				for( j=array[i-1]+1; j<array[i]; j++)
				{
					result+=combineNumber(n-j, k-i-1);
				}
			}
		}
	}
	return result;

}


void lexSuccessor(int n, int k, int* array)
{
	//if i is possible to be negative, don't use size_t!!!!!!!!!!
	int result=0, i,j;
	j=0;

	i=k-1;
	for (i=k-1; i>=0; i--)
	{
		if (array[i]< n-(k-1)+i-1)
		{
			break;
		}
	}
	if (i<0)
	{
		cout<<"undefined";	
		exit(1);
	}
	else
	{
		result=array[i];
		for (j=i; j<k; j++)
		{
			array[j]=result+1+j-i;
		}

	}
}


void displayArray(int* array, int start, int size)
{
	cout<<"[";
	for (int i=start; i<start+size; i++)
	{
		cout<<array[i];
		if (i!=start+size-1)
		{
			cout<<",";
		}
	}
	cout<<"]\n";
}

//assume 
void subsetUnRank(int rank, int n, int k, int* array)
{
	int x=1, temp, r=rank;

	for (int i=0; i<k; i++)
	{
		temp=combineNumber(n-x, k-i-1);
		while (temp<=r)
		{
			r-=temp;
			x++;
			temp=combineNumber(n-x, k-i-1);
		}
		//SetInsert(x-1);
		array[i]=x;
		x++;
	}
}


int increasingUnRank(int rank, int* array)
{
	int r, n, k;
	int temp;
	//assume rank 0 represents empty set
	if (rank==0)
	{
		array[0]=0;
		return 0;
	}
	r=rank;//remove the empty set

	//now to find ground set size
	n=0;
	temp=1;
	while (temp<=r)
	{
		temp*=2;
		n++;
	}
	
	for (k=1; k<=n; k++)
	{
		temp=combineNumber(n, k);
		if (temp<r)
		{
			r-=temp;
		}
		else
		{
			break;
		}
	}
	subsetUnRank(r-1, n, k, array);

	return k;
}

int increasingUnRank(int rank, int n, int* array)
{
	int r, k;
	int temp;
	//assume rank 0 represents empty set
	if (rank==0)
	{
		array[0]=0;
		return 0;
	}
	r=rank;//remove the empty set

	for (k=1; k<=n; k++)
	{
		temp=combineNumber(n, k);
		if (temp<r)
		{
			r-=temp;
		}
		else
		{
			break;
		}
	}
	subsetUnRank(r-1, n, k, array);

	return k;
}





int main()
{
	int k;

	k=increasingUnRank(1999999, 30, array);
	displayArray(array, 0, k);
	




	return 0;
}

//Result:

The result is:
[4,6,12,13,14,15,27]
Press any key to continue2. subset:

file name: question4

#include <iostream>
#include <fstream>
//#include <vector>

using namespace std;

const int MaxNumber=16;

class SimpleSet
{
protected:
	static int size;
	unsigned int data;
public:
	SimpleSet()
	{
		data=0;
	}
	void set(int index)
	{
		unsigned int mask=1;
		data|=(mask<<index);
	}
	void reset(int index)
	{
		unsigned int mask=1;
		data^=(mask<<index);
	}

	void clear()
	{
		data=0;
	}
	bool test(int index) const
	{
		unsigned int mask=1;
		return (data&(mask<<index))!=0;
	}
	void intersect(const SimpleSet& other)
	{
		data&=other.data;		
	}
	int count() const
	{
		int result=0;
		for (int i=0; i<size; i++)
		{
			if (test(i))
			{
				result++;
			}
		}
		return result;
	}
	SimpleSet& operator=(const SimpleSet& other)
	{
		data=other.data;
		return *this;
	}
	int first() const
	{
		int result=-1;
		for (int i=0; i<size; i++)
		{
			if (test(i))
			{
				result= i;
				break;
			}
		}
		return result;
	}
	int last() const
	{
		int result=-1;
		for (int i=size-1; i>=0; i--)
		{
			if (test(i))
			{
				result= i;
				break;
			}
		}
		return result;
	}


	int next(int start) const
	{
		int result=-1;
		for (int i=start+1; i<size; i++)
		{
			if (test(i))
			{
				result= i;
				break;
			}
		}
		return result;
	}
	SimpleSet operator&&(const SimpleSet& other)
	{
		SimpleSet result=*this;
		result.intersect(other);
		return result;
	}
	void display()
	{
		cout<<"[";
		for (int i=0; i<size; i++)
		{
			if (test(i))
			{
				if (i<10)
				{
					cout<<i<<" ";
				}
				else
				{					
					cout<<(char)('a'+(i-10))<<" ";
				}
			}
		}
		cout<<"]\n";
	}
	

};

int SimpleSet::size=MaxNumber;

char nameList[MaxNumber];
SimpleSet A[MaxNumber];
SimpleSet B[MaxNumber];
//SimpleSet C;
SimpleSet result;
SimpleSet current;
int currentMax=0;
int nodeCount;

int currentBound;
int color[MaxNumber];
int colorSize;


int greedyColor(const SimpleSet A[], const SimpleSet& vertex, int color[])
{
	int h, k=0, index=-1, i=0;
	SimpleSet colorClass[MaxNumber];
	SimpleSet temp;

	//index is the next element
	while ((index=vertex.next(index))!=-1)
	{
		h=0;
		while (h<k&&((colorClass[h]&&A[index]&&vertex).count()!=0))
		{
			h++;
		}
		if (h==k)
		{
			k++;
			colorClass[h].clear();
		}
		colorClass[h].set(index);
		color[index]=h;
	}
	return k;
}

void display()
{
	int i, j, count=0;
	cout<<"the name list is:\n";
	for (i=0; i<MaxNumber; i++)
	{
		cout<<nameList[i]<<",";
	}
	cout<<"\n";
	cout<<"the adjacent list is:\n";
	for (i=0; i<MaxNumber; i++)
	{
		for (j=0; j<MaxNumber; j++)
		{
			if (A[i].test(j))
			{
				cout<<"("<<nameList[i]<<","<<nameList[j]<<"),";
				count++;
				if (count%10==0)
				{
					cout<<"\n";
				}
			}
		}
		
	}
}

int element2Index(char ch)
{
	if (ch<='9'&&ch>='0')
	{
		return ch-'0';
	}
	else
	{
		if (ch>='a'&&ch<='z')
		{
			return ch-'a'+10;
		}
		else
		{
			return -1;
		}
	}
}

void readFromFile(char* fileName)
{
	char buf[256];
	char* ptr;
	ifstream in(fileName);

	while (!in.eof())
	{
		in.getline(buf, 256);
		//first call to initialize
		ptr= strtok(buf, ",");
		//to get edge one by one
		while (ptr!=NULL)
		{
			int first=-1, second=-1, i=0;
			while (*(ptr+i)!='\0')
			{
				if (*(ptr+i)!=' ')
				{
					if (first==-1)
					{
						first=element2Index(*(ptr+i));
					}
					else
					{
						second=element2Index(*(ptr+i));
					}
				}
				i++;
			}
			if (first==-1||second==-1)
			{
				cout<<"error in reading edge\n";
				exit(1);
			}
			//get the edge
			A[first].set(second);
			A[second].set(first);
			ptr=strtok(NULL, ",");
		}
		
	}
}

void displayColorTable(int color[], int colorSize)
{
	char ch;
	for (int i=0; i<MaxNumber; i++)
	{
		if (i>9)
		{
			ch='a'+i-10;
		}
		else
		{
			ch='0'+i;
		}
		cout<<"element "<<ch<<" has color "<<color[i]<<endl;
	}
}

void initialize(char* fileName)
{	
	SimpleSet full;
	for (int i=0; i<MaxNumber; i++)
	{
		full.set(i);
		if (i<10)
		{
			nameList[i]='0'+i;
		}
		else
		{
			nameList[i]='a'+i-10;
		}
		for (int j=i+1; j<MaxNumber; j++)
		{
			B[i].set(j);
		}
	}
	readFromFile(fileName);

	//color is out parameter which is an integer array
	colorSize=greedyColor(A, full, color);
	displayColorTable(color, colorSize);
}

int samplingBound(int size, const SimpleSet& choice)
{
	int index=-1, i, result=0;
	int counter[MaxNumber];

	for (i=0; i<MaxNumber; i++)
	{
		counter[i]=0;
	}

	//to count the number of color used in C
	while ((index=choice.next(index))!=-1)
	{
		//flag the color used in C
		counter[color[index]]=1;
	}
	//count color used
	for (i=0; i<MaxNumber; i++)
	{
		result+=counter[i];
	}
	return size+result;
}


int greedyBound(int size, const SimpleSet& choice)
{
	int result;
	int local[MaxNumber];
	result=greedyColor(A, choice, local);
	return result+size;
}



int sizeBound(int size, const SimpleSet& choice)
{
	return size+choice.count();
}


int noBound(int size, const SimpleSet& choice)
{
	return MaxNumber;
}

//pass choice as value!!!!
void doMaxClique(int size, SimpleSet choice, int (*boundFunc)(int, const SimpleSet&))
{
	//static int currentElem;
	nodeCount++;
	int last;
	if (size>currentMax)
	{
		currentMax=size;
		result=current;
	}
	if (size==0)
	{
		for (int i=0; i<MaxNumber; i++)
		{
			choice.set(i);
		}
	}
	else
	{
		last=current.last();
		choice.intersect(A[last]);
		choice.intersect(B[last]);
	}

	currentBound=boundFunc(size, choice);
	
	if (boundFunc==samplingBound&&size==1&&last==8)	
	{
		cout<<"the answer for question 1 is:"<<currentBound<<endl;
	}

	if (currentBound<=currentMax)
	{
		return;
	}
	else
	{
		int index=-1;
		while ((index=choice.next(index))!=-1)
		{
			current.set(index);
			doMaxClique(size+1, choice, boundFunc);
			current.reset(index);
		}
	}
}


void maxClique(int (*boundFunc)(int, const SimpleSet&))
{
	SimpleSet choice;
	currentMax=0;
	nodeCount=0;
	doMaxClique(0, choice, boundFunc);
}





int main( )
{	
	initialize("data1.txt");
	display();

	cout<<"using no bound:\n";
	maxClique(noBound);
	cout<<"nodeCount="<<nodeCount<<"\n";
	result.display();


	cout<<"using size bound:\n";
	maxClique(sizeBound);
	cout<<"nodeCount="<<nodeCount<<"\n";
	result.display();


	cout<<"using sample bound:\n";

	maxClique(samplingBound);
	cout<<"nodeCount="<<nodeCount<<"\n";
	result.display();

	cout<<"using greedy bound:\n";

	maxClique(greedyBound);
	cout<<"nodeCount="<<nodeCount<<"\n";
	result.display();
  
   return 0;
}

//The running result is like this:

element 0 has color 0
element 1 has color 1
element 2 has color 1
element 3 has color 0
element 4 has color 2
element 5 has color 3
element 6 has color 4
element 7 has color 2
element 8 has color 4
element 9 has color 4
element a has color 3
element b has color 0
element c has color 5
element d has color 0
element e has color 5
element f has color 1
the name list is:
0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,
the adjacent list is:
(0,1),(0,2),(0,7),(0,8),(0,9),(0,a),(0,e),(1,0),(1,4),(1,7),
(1,8),(1,9),(1,a),(1,b),(1,c),(1,e),(2,0),(2,3),(2,5),(2,6),
(2,7),(2,8),(2,a),(2,b),(3,2),(3,4),(3,5),(3,6),(3,a),(3,f),
(4,1),(4,3),(4,5),(4,6),(4,8),(4,9),(4,a),(4,e),(5,2),(5,3),
(5,4),(5,6),(5,8),(5,9),(5,b),(5,d),(5,e),(5,f),(6,2),(6,3),
(6,4),(6,5),(6,f),(7,0),(7,1),(7,2),(7,8),(7,a),(7,c),(7,e),
(7,f),(8,0),(8,1),(8,2),(8,4),(8,5),(8,7),(8,b),(8,c),(8,e),
(8,f),(9,0),(9,1),(9,4),(9,5),(9,d),(9,e),(a,0),(a,1),(a,2),
(a,3),(a,4),(a,7),(a,c),(a,d),(a,e),(b,1),(b,2),(b,5),(b,8),
(b,c),(b,e),(b,f),(c,1),(c,7),(c,8),(c,a),(c,b),(c,d),(d,5),
(d,9),(d,a),(d,c),(e,0),(e,1),(e,4),(e,5),(e,7),(e,8),(e,9),
(e,a),(e,b),(e,f),(f,3),(f,5),(f,6),(f,7),(f,8),(f,b),(f,e),
using no bound:
nodeCount=184
[0 1 7 8 e ]
using size bound:
nodeCount=83
[0 1 7 8 e ]
using sample bound:
the answer for question 1 is:4
nodeCount=41
[0 1 7 8 e ]
using greedy bound:
nodeCount=33
[0 1 7 8 e ]
Press any key to continue

//the input data file "data1.txt":

0 1, 0 2, 0 7, 0 8, 0 9, 0 a, 0 e, 1 4, 1 7, 1 8,
1 9, 1 a, 1 b, 1 c, 1 e, 2 3, 2 5, 2 6, 2 7, 2 8,
2 a, 2 b, 3 4, 3 5, 3 6, 3 a, 3 f, 4 5, 4 6, 4 8,
4 9, 4 a, 4 e, 5 6, 5 8, 5 9, 5 b, 5 d, 5 e, 5 f,
6 f, 7 8, 7 a, 7 c, 7 e, 7 f, 8 b, 8 c, 8 e, 8 f,
9 d, 9 e, a c, a d, a e, b c, b e, b f, c d, e f

file name: question5_a

#include <iostream>
#include <fstream>

using namespace std;

const int SquareSize=9;

typedef int Vector[SquareSize];

typedef Vector Square[SquareSize];

struct Coord
{
	int row;
	int col;
};

typedef bool (*SuccessTester)(int row, int col);
typedef bool (*ChoiceMaker)(int row, int col, int& row_next, int& col_next);


Square square;
Square original;
int counter=0;
int nodeCounter=0;
void readFromFile(char* fileName);
void backtrack(int row, int col, SuccessTester successTester, ChoiceMaker choiceMaker);
void printSquare();
bool choiceTester(int row, int col);
bool choiceMaker(int row, int col, int& row_next, int& col_next);

bool successTester(int row, int col);
void question5_a();
void initialize1(int& row, int& col);


int main()
{
	question5_a();

	return 0;
}

void printSquare()
{
	int row, col;
	cout<<"\n";
	for (row=0; row<SquareSize; row++)
	{	
		if (row%3==0)
		{
			cout<<"|-----|-----|-----|\n";
		}	

		for (col=0; col<SquareSize; col++)
		{
			if (col%3==0)
			{
				cout<<"|";
			}
			cout<<square[row][col];
			if ((col+1)%3!=0)
			{
				cout<<" ";
			}
		}
		cout<<"|\n";
	}
	cout<<"|-----|-----|-----|\n";
}

void initialize1(int& row, int& col)
{
	row=col=0;
	counter=0;
	nodeCounter=0;
}


void question5_a()
{
	int row=0, col=0;
	char fileName[10];
	for (int i=2; i<4; i++)
	{
		strcpy(fileName, "data*.txt");
		fileName[4]='0'+i;
		cout<<"**************************************************\n";
		cout<<"\nnow try to solve sudoku of test"<<i<<"\n";
		readFromFile(fileName);
		
		printSquare();
		cout<<"now begin searching solutions:\n\n";
		
		initialize1(row, col);
		backtrack(row, col, successTester, choiceMaker);

		cout<<"\nthe total solutions is :"<<counter<<"\n";
		cout<<"\nthe size of search tree is :"<<nodeCounter<<"\n";
	}

}

bool successTester(int row, int col)
{
	return row==SquareSize;
}

bool choiceMaker(int row, int col, int& row_next, int& col_next)
{
	if (col==SquareSize-1)
	{
		row_next=row+1;
		col_next=0;
	}
	else
	{
		row_next=row;
		col_next=col+1;
	}
	return true;
}

//Originally I try to combine both question into same backtrack,
//So, I use these callback function to generalize a backtrack template
void backtrack(int row, int col, SuccessTester successTester, ChoiceMaker choiceMaker)
{
	//cout<<"row="<<row<<"  col="<<col<<"\n";
	//printSquare();
	int row_next, col_next;
	int oldValue;
	nodeCounter++;
	if (successTester(row, col))
	{
		counter++;
		cout<<"\nthis is "<<counter<<"th solution\n";
		printSquare();
		return;
	}
	
	for (int choice=1; choice<=SquareSize; choice++)
	{
		oldValue=square[row][col];
		square[row][col]=choice;
		
		if (choiceTester(row, col))
		{
			if (choiceMaker(row, col, row_next, col_next))
			{
				backtrack(row_next, col_next, successTester, choiceMaker);
			}
		}
		square[row][col]=oldValue;
	}
}

bool choiceTester(int row, int col)
{
	int i, j;
	int subRowOffset=(row/3)*3;
	int subColOffset=(col/3)*3;

	//the easiest checking
	if (original[row][col]!=0)
	{
		return square[row][col]==original[row][col];
	}



	//check sub grid to see if there is repeat
	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++)
	{
		//check row
		
		if (i!=row && square[i][col]==square[row][col])
		{
			return false;
		}
		//check col
		if (i!=col && square[row][i]==square[row][col])
		{
			return false;
		}

		//check primary diagonal
		if (row==col&& i!=row && square[i][i]==square[row][col])
		{
			return false;
		}

		//check reverse diagonal
		if (row+col==SquareSize-1 && i!=row && square[i][SquareSize-1-i]==square[row][col])
		{
			return false;
		}		
	}

	return true;
}



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
		}
	}
}

************************************************** now try to solve sudoku of test2 |-----|-----|-----| |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: the total solutions is :0 the size of search tree is :2203 ************************************************** now try to solve sudoku of test3 |-----|-----|-----| |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| |-----|-----|-----| now begin searching solutions: this is 1th solution |-----|-----|-----| |1 4 5|7 6 2|9 3 8| |6 2 9|3 8 5|4 7 1| |8 7 3|9 4 1|6 5 2| |-----|-----|-----| |5 1 6|4 3 9|8 2 7| |3 9 7|2 5 8|1 4 6| |2 8 4|1 7 6|5 9 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 2th solution |-----|-----|-----| |1 4 5|7 6 2|9 3 8| |6 2 9|3 8 5|4 7 1| |8 7 3|9 4 1|6 5 2| |-----|-----|-----| |5 1 6|4 7 9|8 2 3| |3 9 7|2 5 8|1 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 3th solution |-----|-----|-----| |1 4 7|2 6 5|9 3 8| |9 2 6|3 4 8|5 7 1| |8 5 3|9 7 1|6 4 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|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 4th solution |-----|-----|-----| |1 4 7|5 6 2|9 3 8| |5 2 6|3 9 8|4 7 1| |8 9 3|7 4 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 5th solution |-----|-----|-----| |1 4 7|5 6 2|9 3 8| |5 2 6|3 9 8|4 7 1| |8 9 3|7 4 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 6th solution |-----|-----|-----| |1 4 7|5 6 2|9 3 8| |9 2 6|3 4 8|5 7 1| |8 5 3|7 9 1|6 4 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|4 5 7| |-----|-----|-----| |5 9 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 7th solution |-----|-----|-----| |1 4 7|5 6 2|9 3 8| |9 2 6|3 4 8|5 7 1| |8 5 3|9 7 1|6 4 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|4 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 8th solution |-----|-----|-----| |1 4 7|5 6 2|9 3 8| |9 2 6|3 4 8|5 7 1| |8 5 3|9 7 1|6 4 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|4 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 9th solution |-----|-----|-----| |1 4 7|9 6 2|5 3 8| |5 2 6|3 4 8|9 7 1| |8 9 3|5 7 1|6 4 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|4 5 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 10th solution |-----|-----|-----| |1 4 7|9 6 2|5 3 8| |5 2 6|3 4 8|9 7 1| |8 9 3|5 7 1|6 4 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|4 5 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 11th solution |-----|-----|-----| |1 4 7|9 6 2|5 3 8| |6 2 5|3 4 8|9 7 1| |8 9 3|5 7 1|6 4 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|4 5 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 12th solution |-----|-----|-----| |1 4 7|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 7 4|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 13th solution |-----|-----|-----| |1 4 7|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 7 4|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 14th solution |-----|-----|-----| |1 4 7|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 7 4|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 15th solution |-----|-----|-----| |1 4 7|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 7 4|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 16th solution |-----|-----|-----| |1 4 7|9 6 2|5 3 8| |9 2 6|3 8 5|4 7 1| |8 5 3|7 4 1|6 9 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|9 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 17th solution |-----|-----|-----| |1 4 7|9 6 2|5 3 8| |9 2 6|3 8 5|4 7 1| |8 5 3|7 4 1|6 9 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|9 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 18th solution |-----|-----|-----| |1 4 7|9 6 5|2 3 8| |5 2 6|3 4 8|9 7 1| |8 9 3|2 7 1|6 4 5| |-----|-----|-----| |6 7 5|4 8 9|1 2 3| |3 1 4|7 5 2|8 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|5 8 2| |4 6 8|5 2 7|3 1 9| |-----|-----|-----| this is 19th solution |-----|-----|-----| |1 4 7|9 6 5|2 3 8| |6 2 5|3 4 8|9 7 1| |8 9 3|2 7 1|6 4 5| |-----|-----|-----| |5 7 6|4 8 9|1 2 3| |3 1 4|7 5 2|8 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|5 8 2| |4 6 8|5 2 7|3 1 9| |-----|-----|-----| this is 20th solution |-----|-----|-----| |1 5 4|7 6 2|9 3 8| |9 2 6|3 8 5|4 7 1| |8 7 3|9 4 1|6 5 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|5 4 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 21th solution |-----|-----|-----| |1 5 4|7 6 2|9 3 8| |9 2 6|3 8 5|4 7 1| |8 7 3|9 4 1|6 5 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|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 22th 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 3 9|8 2 7| |3 7 4|2 5 8|1 9 6| |2 8 9|1 7 6|5 4 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 23th 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 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| |-----|-----|-----| the total solutions is :52 the size of search tree is :70325

#include <iostream> #include <fstream> using namespace std; const int SquareSize=9; typedef int Vector[SquareSize]; typedef Vector Square[SquareSize]; //this is used to record the choice list typedef Square Cube[SquareSize]; Square square; Square original; //the choice number table Square choiceTable; //the choice list Cube cube; int counter=0; int nodeCounter=0; void readFromFile(char* fileName); void backtrack(int row, int col); void printSquare(Square square); bool nextChoice(int& row, int& col); bool successTester(int row, int col); void initializeChoices(); void question5_b(); int main() { //question5_a(); question5_b(); return 0; } void printChoice() { cout<<"\n"; for (int r=0; r<SquareSize; r++) { for (int c=0; c<SquareSize; c++) { cout<<"row["<<r<<"]col["<<c<<"]="; for (int i=0; i<choiceTable[r][c]; i++) { cout<<cube[r][c][i]<<","; } cout<<"\t"; } cout<<"\n"; } } //this function returns -1 if the cell is given a number choice int countChoice(int row, int col) { bool isUsed[SquareSize+1]; int i; int subRow=(row/3)*3; int subCol=(col/3)*3; int r, c, result=0; //if it is given, we assume the number of choice is undefined if (square[row][col]>0) { return -1; } //the zero-index is unused for (i=0; i<SquareSize+1; i++) { isUsed[i]=false; } //because the isUsed array has SquareSize+1, we ignore 0-index for (i=0; i<SquareSize; i++) { //let's count the column first //if square[i][col]==0, then the "isUsed" is unaffected isUsed[square[i][col]]=true; //let's count the row, if square[row][i]==0, it is unused isUsed[square[row][i]]=true; //let's count the small grid r=i/3+subRow; c=i%3+subCol; isUsed[square[r][c]]=true; //now count the primary diagonal if (row==col) { isUsed[square[i][i]]=true; } //now count the reverse diagonal if (row+col==SquareSize-1) { isUsed[square[i][SquareSize-i-1]]=true; } } //we count the number of choice and record them in its array in "cube" for (i=1; i<=SquareSize; i++) { if (!isUsed[i]) { cube[row][col][result]=i; result++; } } return result; } //we simply choose the smallest choice with smallest row or col bool nextChoice(int& row, int& col) { int result=SquareSize+1;//impossible for (int r=0; r<SquareSize; r++) { for (int c=0; c<SquareSize; c++) { if (choiceTable[r][c]>-1) { if (choiceTable[r][c]<result) { result=choiceTable[r][c]; row=r; col=c; } } } } //either no finding, or find 0 choice if (result==SquareSize+1||result==0) { return false; } else { return true; } } //this function will affect all choice related to this row,col //same row, same col, same sub grid, same diagonal, reverse diagonal void updateChoices(int row, int col) { int subRow=(row/3)*3; int subCol=(col/3)*3; int r, c; for (int i=0; i<SquareSize; i++) { //the choice of same row can be affected choiceTable[row][i]=countChoice(row, i); //the choice of same col can be affected choiceTable[i][col]=countChoice(i, col); //the choice of sub grid can be affected r=i/3+subRow; c=i%3+subCol; choiceTable[r][c]=countChoice(r, c); //if it is in primary diagonal if (row==col) { choiceTable[i][i]=countChoice(i, i); } //if it is in reverse diagonal if (row+col==SquareSize-1) { choiceTable[i][SquareSize-i-1]=countChoice(i, SquareSize-1-i); } } } void initializeChoices() { for (int r=0; r<SquareSize; r++) { for (int c=0; c<SquareSize; c++) { choiceTable[r][c]=countChoice(r, c); } } } void initialize(int& row, int& col) { counter=0; nodeCounter=0; initializeChoices(); //printSquare(choiceTable); //printChoice(); nextChoice(row, col); } void question5_b() { int row=0, col=0; char fileName[10]; for (int i=2; i<4; i++) { strcpy(fileName, "data*.txt"); fileName[4]='0'+i; cout<<"**************************************************\n"; cout<<"\nnow try to solve sudoku of test"<<i<<"\n"; readFromFile(fileName); printSquare(square); cout<<"now begin searching solutions:\n\n"; initialize(row, col); backtrack(row, col); cout<<"\nthe total solutions is :"<<counter<<"\n"; cout<<"\nthe size of search tree is :"<<nodeCounter<<"\n"; } } void printSquare(Square square) { int row, col; cout<<"\n"; for (row=0; row<SquareSize; row++) { if (row%3==0) { cout<<"|-----|-----|-----|\n"; } for (col=0; col<SquareSize; col++) { if (col%3==0) { cout<<"|"; } cout<<square[row][col]; if ((col+1)%3!=0) { cout<<" "; } } cout<<"|\n"; } cout<<"|-----|-----|-----|\n"; } bool successTester(int row, int col) { for (int r=0; r<SquareSize; r++) { for (int c=0; c<SquareSize; c++) { if (square[r][c]==0) { return false; } } } return true; } void backtrack(int row, int col) { //cout<<"row="<<row<<" col="<<col<<"\n"; //printSquare(); int row_next, col_next; int oldValue, choiceNumber, choice; nodeCounter++; //we must keep this local variable, because after //call updateChoice, the choiceTable will become -1; choiceNumber=choiceTable[row][col]; for (int i=0; i<choiceNumber; i++) { oldValue=square[row][col]; choice=cube[row][col][i]; square[row][col]=choice; updateChoices(row, col); //printSquare(choiceTable); //there is no need choice tester because after //updating choices, those non-fit choices are filtered if (successTester(row, col)) { counter++; cout<<"\nthis is "<<counter<<"th solution\n"; printSquare(square); } else { if (nextChoice(row_next, col_next)) { backtrack(row_next, col_next); } } square[row][col]=oldValue; updateChoices(row, col); } } 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 } } }

************************************************** now try to solve sudoku of test2 |-----|-----|-----| |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: the total solutions is :0 the size of search tree is :1 ************************************************** now try to solve sudoku of test3 |-----|-----|-----| |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| |-----|-----|-----| now begin searching solutions: this is 1th 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 2th 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 3th 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 4th solution |-----|-----|-----| |1 4 7|5 6 2|9 3 8| |9 2 6|3 4 8|5 7 1| |8 5 3|7 9 1|6 4 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|4 5 7| |-----|-----|-----| |5 9 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 5th solution |-----|-----|-----| |1 4 7|5 6 2|9 3 8| |9 2 6|3 4 8|5 7 1| |8 5 3|9 7 1|6 4 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|4 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 6th solution |-----|-----|-----| |1 4 7|5 6 2|9 3 8| |9 2 6|3 4 8|5 7 1| |8 5 3|9 7 1|6 4 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|4 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 7th 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 8th 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 9th 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 10th 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 11th 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 12th 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 13th 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 14th 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 15th solution |-----|-----|-----| |1 4 7|9 6 2|5 3 8| |5 2 6|3 4 8|9 7 1| |8 9 3|5 7 1|6 4 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|4 5 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 16th solution |-----|-----|-----| |1 4 7|9 6 2|5 3 8| |5 2 6|3 4 8|9 7 1| |8 9 3|5 7 1|6 4 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|4 5 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 17th solution |-----|-----|-----| |1 4 7|9 6 2|5 3 8| |6 2 5|3 4 8|9 7 1| |8 9 3|5 7 1|6 4 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|4 5 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 18th solution |-----|-----|-----| |1 4 7|5 6 2|9 3 8| |5 2 6|3 9 8|4 7 1| |8 9 3|7 4 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 19th solution |-----|-----|-----| |1 4 7|5 6 2|9 3 8| |5 2 6|3 9 8|4 7 1| |8 9 3|7 4 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 20th 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 21th 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 22th 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 23th 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 24th solution |-----|-----|-----| |1 4 5|7 6 2|9 3 8| |6 2 9|3 8 5|4 7 1| |8 7 3|9 4 1|6 5 2| |-----|-----|-----| |5 1 6|4 3 9|8 2 7| |3 9 7|2 5 8|1 4 6| |2 8 4|1 7 6|5 9 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 25th solution |-----|-----|-----| |1 4 5|7 6 2|9 3 8| |6 2 9|3 8 5|4 7 1| |8 7 3|9 4 1|6 5 2| |-----|-----|-----| |5 1 6|4 7 9|8 2 3| |3 9 7|2 5 8|1 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 26th solution |-----|-----|-----| |1 5 4|7 6 2|9 3 8| |9 2 6|3 8 5|4 7 1| |8 7 3|9 4 1|6 5 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|5 4 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 27th solution |-----|-----|-----| |1 5 4|7 6 2|9 3 8| |9 2 6|3 8 5|4 7 1| |8 7 3|9 4 1|6 5 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|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 28th 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 3 9|8 2 7| |3 7 4|2 5 8|1 9 6| |2 8 9|1 7 6|5 4 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 29th 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 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 30th 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 31th 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 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 4 7|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 7 4|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 35th solution |-----|-----|-----| |1 4 7|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 7 4|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 36th solution |-----|-----|-----| |1 4 7|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 7 4|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 37th solution |-----|-----|-----| |1 4 7|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 7 4|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 38th solution |-----|-----|-----| |1 4 7|9 6 2|5 3 8| |9 2 6|3 8 5|4 7 1| |8 5 3|7 4 1|6 9 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|9 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 39th solution |-----|-----|-----| |1 4 7|9 6 2|5 3 8| |9 2 6|3 8 5|4 7 1| |8 5 3|7 4 1|6 9 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|9 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 40th 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 41th 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 42th 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 43th 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 44th 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 45th 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 46th 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 47th 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 48th solution |-----|-----|-----| |1 4 7|2 6 5|9 3 8| |9 2 6|3 4 8|5 7 1| |8 5 3|9 7 1|6 4 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|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 49th solution |-----|-----|-----| |1 4 7|9 6 5|2 3 8| |5 2 6|3 4 8|9 7 1| |8 9 3|2 7 1|6 4 5| |-----|-----|-----| |6 7 5|4 8 9|1 2 3| |3 1 4|7 5 2|8 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|5 8 2| |4 6 8|5 2 7|3 1 9| |-----|-----|-----| this is 50th solution |-----|-----|-----| |1 4 7|9 6 5|2 3 8| |6 2 5|3 4 8|9 7 1| |8 9 3|2 7 1|6 4 5| |-----|-----|-----| |5 7 6|4 8 9|1 2 3| |3 1 4|7 5 2|8 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|5 8 2| |4 6 8|5 2 7|3 1 9| |-----|-----|-----| this is 51th 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 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| |-----|-----|-----| the total solutions is :52 the size of search tree is :1605

#include <iostream> #include <fstream> using namespace std; const int SquareSize=9; const int MaxDepth=SquareSize*SquareSize; const int MaxRunNumber=100; typedef int Vector[SquareSize]; typedef Vector Square[SquareSize]; //this is used to record the choice list typedef Square Cube[SquareSize]; Square square; Square original; //the choice number table Square choiceTable; //the choice list Cube cube; double levelSize[MaxDepth+1]; int runSize[MaxDepth+1]; int counter=0; int totalSize=0; int nodeCounter=0; int deadCounter=0; int runCounter=0; int depth=0; double treeNumber=0; int deepest=0; void readFromFile(char* fileName); void backtrack(int row, int col); void printSquare(Square square); bool nextChoice(int& row, int& col); bool successTester(int row, int col); void initializeChoices(); void question5_b(); int main() { //question5_a(); question5_b(); return 0; } void printChoice() { cout<<"\n"; for (int r=0; r<SquareSize; r++) { for (int c=0; c<SquareSize; c++) { cout<<"row["<<r<<"]col["<<c<<"]="; for (int i=0; i<choiceTable[r][c]; i++) { cout<<cube[r][c][i]<<","; } cout<<"\t"; } cout<<"\n"; } } //this function returns -1 if the cell is given a number choice int countChoice(int row, int col) { bool isUsed[SquareSize+1]; int i; int subRow=(row/3)*3; int subCol=(col/3)*3; int r, c, result=0; //if it is given, we assume the number of choice is undefined if (square[row][col]>0) { return -1; } //the zero-index is unused for (i=0; i<SquareSize+1; i++) { isUsed[i]=false; } //because the isUsed array has SquareSize+1, we ignore 0-index for (i=0; i<SquareSize; i++) { //let's count the column first //if square[i][col]==0, then the "isUsed" is unaffected isUsed[square[i][col]]=true; //let's count the row, if square[row][i]==0, it is unused isUsed[square[row][i]]=true; //let's count the small grid r=i/3+subRow; c=i%3+subCol; isUsed[square[r][c]]=true; //now count the primary diagonal if (row==col) { isUsed[square[i][i]]=true; } //now count the reverse diagonal if (row+col==SquareSize-1) { isUsed[square[i][SquareSize-i-1]]=true; } } //we count the number of choice and record them in its array in "cube" for (i=1; i<=SquareSize; i++) { if (!isUsed[i]) { cube[row][col][result]=i; result++; } } return result; } //we simply choose the smallest choice with smallest row or col bool nextChoice(int& row, int& col) { int result=SquareSize+1;//impossible for (int r=0; r<SquareSize; r++) { for (int c=0; c<SquareSize; c++) { if (choiceTable[r][c]>-1) { if (choiceTable[r][c]<result) { result=choiceTable[r][c]; row=r; col=c; } } } } //either no finding, or find 0 choice if (result==SquareSize+1||result==0) { return false; } else { return true; } } //this function will affect all choice related to this row,col //same row, same col, same sub grid, same diagonal, reverse diagonal void updateChoices(int row, int col) { int subRow=(row/3)*3; int subCol=(col/3)*3; int r, c; for (int i=0; i<SquareSize; i++) { //the choice of same row can be affected choiceTable[row][i]=countChoice(row, i); //the choice of same col can be affected choiceTable[i][col]=countChoice(i, col); //the choice of sub grid can be affected r=i/3+subRow; c=i%3+subCol; choiceTable[r][c]=countChoice(r, c); //if it is in primary diagonal if (row==col) { choiceTable[i][i]=countChoice(i, i); } //if it is in reverse diagonal if (row+col==SquareSize-1) { choiceTable[i][SquareSize-i-1]=countChoice(i, SquareSize-1-i); } } } void initializeChoices() { for (int r=0; r<SquareSize; r++) { for (int c=0; c<SquareSize; c++) { choiceTable[r][c]=countChoice(r, c); } } } void initialize(int& row, int& col) { counter=0; nodeCounter=0; deadCounter=0; runCounter=0; depth=0; totalSize=0; deepest=0; treeNumber=0; for (int i=1; i<MaxDepth+1; i++) { levelSize[i]=0; runSize[i]=0; } levelSize[0]=1; runSize[0]=1; initializeChoices(); //printSquare(choiceTable); //printChoice(); nextChoice(row, col); } void question5_b() { int row=0, col=0; char fileName[10]; for (int i=3; i<5; i++) { strcpy(fileName, "data*.txt"); fileName[4]='0'+i; cout<<"**************************************************\n"; cout<<"\nnow try to solve sudoku of test"<<i<<"\n"; readFromFile(fileName); printSquare(square); cout<<"now begin searching solutions:\n\n"; initialize(row, col); backtrack(row, col); //cout<<"\nthe total solutions is :"<<counter<<"\n"; //cout<<"\nthe size of search tree is :"<<nodeCounter<<"\n"; //cout<<"\nthe total dead end is :"<<deadCounter<<"\n"; cout<<"\nthe number of estimated runs is:"<<MaxRunNumber<<"\n"; cout<<"\nnow print the estimated size of each level:\n"; for (int i=0; i<deepest; i++) { //cout<<"\nthe sum size of level "<<i<<" is:"<<levelSize[i]<<"\n"; levelSize[i]/=MaxRunNumber; totalSize+=levelSize[i]; cout<<"estimated size of level "<<i<<" is:"<<levelSize[i]<<"\n"; } //totalSize/=MaxRunNumber; treeNumber/=MaxRunNumber; cout<<"\nthe total estimated size of backtrack search tree is:"<<totalSize<<"\n"; cout<<"\nthe estimated number of solutions is:"<<treeNumber*counter/MaxRunNumber<<"\n"; cout<<"\nthe number of solutions generated in this estimation:"<<counter<<"\n"; } } void printSquare(Square square) { int row, col; cout<<"\n"; for (row=0; row<SquareSize; row++) { if (row%3==0) { cout<<"|-----|-----|-----|\n"; } for (col=0; col<SquareSize; col++) { if (col%3==0) { cout<<"|"; } cout<<square[row][col]; if ((col+1)%3!=0) { cout<<" "; } } cout<<"|\n"; } cout<<"|-----|-----|-----|\n"; } bool successTester(int row, int col) { for (int r=0; r<SquareSize; r++) { for (int c=0; c<SquareSize; c++) { if (square[r][c]==0) { return false; } } } return true; } void addLevel() { double treeSize=1; for (int i=0; i<depth; i++) { treeSize*=runSize[i]; levelSize[i]+=treeSize; } if (depth>deepest) { deepest=depth; } treeNumber+=treeSize; //totalSize+=treeSize; } void backtrack(int row, int col) { //cout<<"row="<<row<<" col="<<col<<"\n"; //printSquare(); int row_next, col_next; int oldValue, choiceNumber, choice; nodeCounter++; depth++; //we must keep this local variable, because after //call updateChoice, the choiceTable will become -1; choiceNumber=choiceTable[row][col]; //cout<<"current depth="<<depth<<" with choices of "<<choiceNumber<<"\n"; runSize[depth]=choiceNumber; for (int i=0; i<choiceNumber; i++) { oldValue=square[row][col]; choice=cube[row][col][i]; square[row][col]=choice; updateChoices(row, col); //printSquare(choiceTable); //we stop when we reach the maximum run number if (runCounter==MaxRunNumber) { break; } //there is no need choice tester because after //updating choices, those non-fit choices are filtered if (successTester(row, col)) { counter++; runCounter++; //this is a successful run, so we count the size of each level addLevel(); //cout<<"\nthis is "<<counter<<"th solution\n"; //printSquare(square); } else { if (nextChoice(row_next, col_next)) { backtrack(row_next, col_next); } else { runCounter++;//this is also a run deadCounter++; //this is a dead end run, we also need to count the size of level addLevel(); //cout<<"deadend of "<<deadCounter<<"\n"; //printSquare(choiceTable); //this should be the dead end } } square[row][col]=oldValue; updateChoices(row, col); } depth--; } 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 } } }

************************************************** now try to solve sudoku of test3 |-----|-----|-----| |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| |-----|-----|-----| now begin searching solutions: the number of estimated runs is:100 now print the estimated size of each level: estimated size of level 0 is:1.01 estimated size of level 1 is:2 estimated size of level 2 is:3.7 estimated size of level 3 is:6.06 estimated size of level 4 is:8.46 estimated size of level 5 is:13.56 estimated size of level 6 is:19.6 estimated size of level 7 is:27.92 estimated size of level 8 is:27.92 estimated size of level 9 is:47.12 estimated size of level 10 is:53.2 estimated size of level 11 is:59.12 estimated size of level 12 is:71.6 estimated size of level 13 is:79.92 estimated size of level 14 is:80.56 estimated size of level 15 is:83.44 estimated size of level 16 is:86 estimated size of level 17 is:86.64 estimated size of level 18 is:86.64 estimated size of level 19 is:91.04 estimated size of level 20 is:98.4 estimated size of level 21 is:96.32 estimated size of level 22 is:95.04 estimated size of level 23 is:96.32 estimated size of level 24 is:96 estimated size of level 25 is:109.76 estimated size of level 26 is:128.32 estimated size of level 27 is:142.08 estimated size of level 28 is:147.84 estimated size of level 29 is:155.52 estimated size of level 30 is:154.88 estimated size of level 31 is:162.24 estimated size of level 32 is:150.72 estimated size of level 33 is:152.64 estimated size of level 34 is:149.76 estimated size of level 35 is:174.08 estimated size of level 36 is:143.36 estimated size of level 37 is:143.36 estimated size of level 38 is:135.68 estimated size of level 39 is:105.28 estimated size of level 40 is:107.84 estimated size of level 41 is:107.84 estimated size of level 42 is:102.72 estimated size of level 43 is:102.72 estimated size of level 44 is:121.92 estimated size of level 45 is:121.92 estimated size of level 46 is:146.88 estimated size of level 47 is:145.6 estimated size of level 48 is:155.84 estimated size of level 49 is:155.84 estimated size of level 50 is:285.12 estimated size of level 51 is:285.12 estimated size of level 52 is:285.12 the total estimated size of backtrack search tree is:5672 the estimated number of solutions is:214.037 the number of solutions generated in this estimation:51 ************************************************** now try to solve sudoku of test4 |-----|-----|-----| |0 0 0|0 0 0|0 0 0| |0 0 0|0 0 0|0 0 0| |0 0 0|0 0 0|0 0 0| |-----|-----|-----| |0 0 0|0 0 0|0 0 0| |0 0 0|0 0 0|0 0 0| |0 0 0|0 0 0|0 0 0| |-----|-----|-----| |0 0 0|0 0 0|0 0 0| |0 0 0|0 0 0|0 0 0| |0 0 0|0 0 0|0 0 0| |-----|-----|-----| now begin searching solutions: the number of estimated runs is:100 now print the estimated size of each level: estimated size of level 0 is:1.01 estimated size of level 1 is:9 estimated size of level 2 is:72 estimated size of level 3 is:504 estimated size of level 4 is:3024 estimated size of level 5 is:15120 estimated size of level 6 is:60480 estimated size of level 7 is:181440 estimated size of level 8 is:362880 estimated size of level 9 is:362880 estimated size of level 10 is:2.17728e+006 estimated size of level 11 is:1.08864e+007 estimated size of level 12 is:4.35456e+007 estimated size of level 13 is:1.30637e+008 estimated size of level 14 is:2.61274e+008 estimated size of level 15 is:2.61274e+008 estimated size of level 16 is:7.83821e+008 estimated size of level 17 is:1.56764e+009 estimated size of level 18 is:1.56764e+009 estimated size of level 19 is:4.70292e+009 estimated size of level 20 is:9.40585e+009 estimated size of level 21 is:9.40585e+009 estimated size of level 22 is:2.82175e+010 estimated size of level 23 is:5.64351e+010 estimated size of level 24 is:5.64351e+010 estimated size of level 25 is:1.69305e+011 estimated size of level 26 is:3.38611e+011 estimated size of level 27 is:3.38611e+011 estimated size of level 28 is:1.01583e+012 estimated size of level 29 is:3.0475e+012 estimated size of level 30 is:6.09499e+012 estimated size of level 31 is:1.219e+013 estimated size of level 32 is:2.438e+013 estimated size of level 33 is:2.438e+013 estimated size of level 34 is:4.87599e+013 estimated size of level 35 is:9.75198e+013 estimated size of level 36 is:1.9504e+014 estimated size of level 37 is:1.9504e+014 estimated size of level 38 is:1.9504e+014 estimated size of level 39 is:3.90079e+014 estimated size of level 40 is:3.90079e+014 estimated size of level 41 is:7.80159e+014 estimated size of level 42 is:7.80159e+014 estimated size of level 43 is:1.56032e+015 estimated size of level 44 is:1.56032e+015 estimated size of level 45 is:3.12064e+015 estimated size of level 46 is:6.24127e+015 estimated size of level 47 is:1.22953e+016 estimated size of level 48 is:2.21565e+016 estimated size of level 49 is:2.36544e+016 estimated size of level 50 is:2.60261e+016 estimated size of level 51 is:4.07555e+016 estimated size of level 52 is:4.27527e+016 estimated size of level 53 is:4.17541e+016 estimated size of level 54 is:4.15044e+016 estimated size of level 55 is:4.12548e+016 estimated size of level 56 is:4.09427e+016 estimated size of level 57 is:4.20662e+016 estimated size of level 58 is:4.20662e+016 estimated size of level 59 is:4.20662e+016 estimated size of level 60 is:4.1442e+016 estimated size of level 61 is:4.09427e+016 estimated size of level 62 is:4.04434e+016 estimated size of level 63 is:4.1442e+016 estimated size of level 64 is:4.11924e+016 estimated size of level 65 is:3.89455e+016 estimated size of level 66 is:4.99302e+016 estimated size of level 67 is:4.94309e+016 estimated size of level 68 is:4.84323e+016 estimated size of level 69 is:7.2898e+016 estimated size of level 70 is:7.2898e+016 estimated size of level 71 is:7.18994e+016 estimated size of level 72 is:7.18994e+016 estimated size of level 73 is:7.09008e+016 estimated size of level 74 is:1.05852e+017 estimated size of level 75 is:1.05852e+017 estimated size of level 76 is:1.05852e+017 estimated size of level 77 is:1.05852e+017 estimated size of level 78 is:2.01718e+017 estimated size of level 79 is:2.01718e+017 estimated size of level 80 is:2.01718e+017 the total estimated size of backtrack search tree is:559348512 the estimated number of solutions is:1.32003e+017 the number of solutions generated in this estimation:60