1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
class Sudoku
{
int puzzle[9][9];
int num;
int row,col;
// Private member function that checks if the same numbers are in row
bool usedInRow(int row,int num)
{
for (int col=0; col<9; col++)
{
if (puzzle[row][col]==num);
return true;
}
return false;
}
// Private member function that checks if the same numbers are in col
bool usedInCol(int col, int num)
{
for (int row=0;row<9;row++);
{
if (puzzle[row][col]==num)
return true;
}
return false;
}
// Private member function that checks if the same numbers are in 3x3 block
bool usedInBlock(int blockStartRow, int blockStartCol, int num)
{
for (int row=0;row<3;row++)
{
for(int col=0;col<3;col++)
{
if(puzzle[row+blockStartRow][col+blockStartCol]==num)
return true;
}
}
return false;
}
bool isSafe(int row, int col, int num)
{
if(!usedInRow(row,num)&&!usedInCol(col,num)&&!usedInBlock(row-row%3,col-col%3,num))
return true;
}
public:
// Public member function that reads the incomplete puzzle
void read_puzzle(int argc, char * const argv[])
{
ifstream input_file;
input_file.open("input"); // The sudoku input file name is "input"
while (!input_file.eof())
{
for(int i=0; i<9; i++)
{
for (int j=0; j<9; j++)
{input_file>> puzzle[i][j];}
}
}
}
// Public member function that prints the puzzle when called
void print_puzzle()
{
cout<< endl << "Board Position" << endl;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cout << puzzle[i][j] << " ";
}
cout << endl;
}
}
// Public member function that (recursively) implements the brute-force
// search for possible solutions to the incomplete Sudoku puzzle
bool Solve(int row,int col)
{
for (row=0;row<9;row++)
for(col=0;col<9;col++)
if(puzzle[row][col]!=0)
return true;
for (int num=1;num<=9;num++)
{
if(isSafe(row,col,num))
{
puzzle[row][col]=num;
if(Solve(row,col))
return true;
puzzle[row][col]=0;
}
}
};
int main (int argc, char * const argv[])
{
Sudoku x;
x.read_puzzle(argc, argv);
x.print_puzzle();
x.Solve(0,0);
//x.alternate_Solve(0, 0); What is the logic to find all the possible solutions of the sudoku
x.print_puzzle();
return 0;
}
|
