Combinatorial Algorithm Final Exam
A. First Edition
This is the final exam of comp6661 and they are a bunch of small programs. All of them are not particularly difficult.
However, it still takes some time. And I think 48 hours is a reasonable time to finish it because 24 hours would be a
little bit too harsh to finish, considering that I need to do my jogging, PC gaming, watching web TV etc.
¡¡
.
E.Further improvement
¡¡
F.File listing
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
}
}
}
The input data file "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
The input data file "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
The running result:
************************************************** 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
file name: question5_b
#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
}
}
}
¡¡
The input data file "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
The input data file "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
The running result:
************************************************** 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
¡¡
file name: question5_c
#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
}
}
}
¡¡
The input data file "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
The input data file "data4.txt":
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
The running result:
************************************************** 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
¡¡
¡¡