-
Notifications
You must be signed in to change notification settings - Fork 0
/
sudoku_recursion
295 lines (284 loc) · 7.35 KB
/
sudoku_recursion
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
#ifndef sudoku
#define sudoku
#include <vector>
#include <fstream>
#include <iostream>
using std::vector;
using namespace std;
class Sudoku
{
// Private
int puzzle[9][9];
// Private member function that checks if the named row is valid
int count = 0; // count the number of solutions
bool row_valid(int row)
{
int i, j;
int judge = 1;
for (i = 0; i < 8; i++)
for (j = (i + 1); j < 9; j++) // check if entries after i is equal to i
if ((puzzle[row][j] != 0) && (puzzle[row][i] != 0)) // if these entires are not empty
if (puzzle[row][j] == puzzle[row][i])
{
judge = 0;
break;
}
if (judge)
return true;
else
return false;
// write code that checks if "row" is valid
}
// Private member function that checks if the named column is valid
bool col_valid(int col)
{
int i, j;
int judge = 1;
for (i = 0; i < 8; i++)
for (j = (i + 1); j < 9; j++) // check if entries after i is equal to i
if ((puzzle[j][col] != 0) && (puzzle[i][col] != 0)) // if these entires are not empty
if (puzzle[j][col] == puzzle[i][col])
{
judge = 0;
break;
}
if (judge)
return true;
else
return false;// check validity of "col"
}
// Private member function that checks if the named 3x3 block is valid
bool block_valid(int row, int col)
{
vector <int> block_entry; // use this to contain 9 entries in a block
int judge = 1;
int i, j;
if ((row >= 0) && (row <= 2)) // first 3 row's blocks
{
if ((col >= 0) && (col <= 2)) //(1,1) block
{
for (i = 0; i <= 2; i++)
for (j = 0; j <= 2; j++)
block_entry.push_back(puzzle[i][j]);
for (i = 0; i <= 7; i++)
for (j = (i + 1); j <= 8; j++)
if ((block_entry[i] != 0) && (block_entry[j] != 0))
if (block_entry[j] == block_entry[i])
{
judge = 0;
break;
}
}
if ((col >= 3) && (col <= 5)) //(1,2) block
{
for (i = 0; i <= 2; i++)
for (j = 3; j <= 5; j++)
block_entry.push_back(puzzle[i][j]);
for (i = 0; i <= 7; i++)
for (j = (i + 1); j <= 8; j++)
if ((block_entry[i] != 0) && (block_entry[j] != 0))
if (block_entry[j] == block_entry[i])
{
judge = 0;
break;
}
}
if ((col >= 6) && (col <= 8)) //(1,3) block
{
for (i = 0; i <= 2; i++)
for (j = 6; j <= 8; j++)
block_entry.push_back(puzzle[i][j]);
for (i = 0; i <= 7; i++)
for (j = (i + 1); j <= 8; j++)
if ((block_entry[i] != 0) && (block_entry[j] != 0))
if (block_entry[j] == block_entry[i])
{
judge = 0;
break;
}
}
}
if ((row >= 3) && (row <= 5)) // next 3 row's blocks
{
if ((col >= 0) && (col <= 2)) //(2,1) block
{
for (i = 3; i <= 5; i++)
for (j = 0; j <= 2; j++)
block_entry.push_back(puzzle[i][j]);
for (i = 0; i <= 7; i++)
for (j = (i + 1); j <= 8; j++)
if ((block_entry[i] != 0) && (block_entry[j] != 0))
if (block_entry[j] == block_entry[i])
{
judge = 0;
break;
}
}
if ((col >= 3) && (col <= 5)) //(2,2) block
{
for (i = 3; i <= 5; i++)
for (j = 3; j <= 5; j++)
block_entry.push_back(puzzle[i][j]);
for (i = 0; i <= 7; i++)
for (j = (i + 1); j <= 8; j++)
if ((block_entry[i] != 0) && (block_entry[j] != 0))
if (block_entry[j] == block_entry[i])
{
judge = 0;
break;
}
}
if ((col >= 6) && (col <= 8)) //(2,3) block
{
for (i = 3; i <= 5; i++)
for (j = 6; j <= 8; j++)
block_entry.push_back(puzzle[i][j]);
for (i = 0; i <= 7; i++)
for (j = (i + 1); j <= 8; j++)
if ((block_entry[i] != 0) && (block_entry[j] != 0))
if (block_entry[j] == block_entry[i])
{
judge = 0;
break;
}
}
}
if ((row >= 6) && (row <= 8)) // last 3 row's blocks
{
if ((col >= 0) && (col <= 2)) //(3,1) block
{
for (i = 6; i <= 8; i++)
for (j = 0; j <= 2; j++)
block_entry.push_back(puzzle[i][j]);
for (i = 0; i <= 7; i++)
for (j = (i + 1); j <= 8; j++)
if ((block_entry[i] != 0) && (block_entry[j] != 0))
if (block_entry[j] == block_entry[i])
{
judge = 0;
break;
}
}
if ((col >= 3) && (col <= 5)) //(3,2) block
{
for (i = 6; i <= 8; i++)
for (j = 3; j <= 5; j++)
block_entry.push_back(puzzle[i][j]);
for (i = 0; i <= 7; i++)
for (j = (i + 1); j <= 8; j++)
if ((block_entry[i] != 0) && (block_entry[j] != 0))
if (block_entry[j] == block_entry[i])
{
judge = 0;
break;
}
}
if ((col >= 6) && (col <= 8)) //(3,3) block
{
for (i = 6; i <= 8; i++)
for (j = 6; j <= 8; j++)
block_entry.push_back(puzzle[i][j]);
for (i = 0; i <= 7; i++)
for (j = (i + 1); j <= 8; j++)
if ((block_entry[i] != 0) && (block_entry[j] != 0))
if (block_entry[j] == block_entry[i])
{
judge = 0;
break;
}
}
}
if (judge)
return true;
else
return false;
// check 3 x 3 block validity
}
// Public member function that reads the incomplete puzzle
// we are not doing any checks on the input puzzle -- that is,
// we are assuming they are indeed valid
public:
void read_puzzle(int argc, char * const argv[])
{
int value_just_read_from_file;
vector <int> P;
ifstream input_file(argv[1]);
if (input_file.is_open())
{
while (input_file >> value_just_read_from_file)
{
P.push_back(value_just_read_from_file);
}
}
else
{
std::cout << "input file does not exist" << std::endl;
}
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
puzzle[i][j] = P[j + i * 9];
// write code that reads the input puzzle using the
// guidelines of figure 23 of the bootcamp material
}
// Public member function that prints the puzzle when called
void print_puzzle()
{
std::cout << std::endl << "Board Position and solution: " << count <<std::endl;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
// check if we have a legitimate integer between 1 and 9
if ((puzzle[i][j] >= 1) && (puzzle[i][j] <= 9))
{
// printing initial value of the puzzle with some formatting
std::cout << puzzle[i][j] << " ";
}
else {
// printing initial value of the puzzle with some formatting
std::cout << "X ";
}
}
std::cout << std::endl;
}
count++;
}
// Public member function that (recursively) implements the brute-force
// search for possible solutions to the incomplete Sudoku puzzle
bool Solve(int row, int col)
{
int judge = 1;
int i, j, k;
int temp_i, temp_j;
for (temp_i = 0; temp_i < 9; temp_i++)
for (temp_j = 0; temp_j < 9; temp_j++)
if (0 == puzzle[temp_i][temp_j])
{
judge = 0;
i = temp_i;
j = temp_j; // record current position
goto breakloop;
}
print_puzzle();
return true;
breakloop:
{
for (k = 1; k <= 9; k++)
{
puzzle[i][j] = k;
if ((row_valid(i)) && (col_valid(j)) && (block_valid(i, j)) && (Solve(i, j)))
{
//return true;
}
}
puzzle[i][j] = 0;
return false;
}
// this part of the code identifies the row and col number of the
// first incomplete (i.e. 0) entry in the puzzle. If the puzzle has
// no zeros, the variable row will be 9 => the puzzle is done, as
// each entry is row-, col- and block-valid...
// use the pseudo code of figure 3 of the description
}
};
#endif