-
Notifications
You must be signed in to change notification settings - Fork 9
/
Copy pathSudokuSolver.cc
335 lines (314 loc) · 14.1 KB
/
SudokuSolver.cc
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
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
/*
******************************************************************************
*
* fileName : SudokuSolver.cc
*
* Author : Aniket Awati <[email protected]>
* Modified By : Aditya Shevade <[email protected]>
*
* Version : 2.0.0
* Created : 10/11/2009
* Modified : 12/06/2011
*
* Description : This class solves SuDoKu puzzles. It receives a 2D array
* during initialization (via constructor). The empty cells
* in the puzzle can have any random value. The class will
* ignore them while reading the input.
*
* The constructor itself calls the initialization methods
* followed by the solvers and finally writes the input array
* (using a reference call - does not return anything).
*
* License : This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
* Changelog :
* 12/06/2011 : Added license.
* Cleaned up the code.
*
******************************************************************************
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
class SudokuSolver {
public:
int NUM; // Constant 9
int ROW; // Constant 3
int COL; // Constant 3
int BLK; // Constant 3
int problemMatrix [9][9]; // Main problem matrix
bool tagRow [9][9]; // Row tags
bool tagCol [9][9]; // Column tags
bool tagBlk [9][9]; // Block tags
SudokuSolver (int (&inputMatrix) [9][9]) {
NUM = 9;
ROW = 3;
COL = 3;
BLK = 3;
initTag ();
initPuzzle ();
for (int j = 0; j < NUM; j++)
for (int k = 0; k < NUM; k++) {
if (inputMatrix[j][k] < 1 || inputMatrix[j][k] > NUM)
continue;
else
problemMatrix [j][k] = inputMatrix [j][k];
}
fillTags();
if (solvePuzzle ()) {
for (int j = 0; j < NUM; j++)
for (int k = 0; k < NUM; k++)
inputMatrix [j][k] = problemMatrix [j][k];
}
else {
cerr << "Error: Puzzle cannot be solved." << endl;
exit (1);
}
}
/* This function initializes all the tags to false (as in empty). The tags
* are later used to determine if a number is valid in a row, column or
* block. Whenever the number is filled, the corresponding tags are set.
*/
void initTag (void) {
for (int j = 0; j < NUM; j++) {
for (int k = 0; k < NUM; k++) {
tagRow[j][k] = false;
tagCol[j][k] = false;
tagBlk[j][k] = false;
}
}
}
/* This function makes all the cells of the main problem matrix zero.
* It is not really required if the input to the class already has
* zeroes in place instead of empty / garbage cells.
*/
void initPuzzle (void) {
for (int j = 0; j < NUM; j++) {
for (int k = 0; k < NUM; k++) {
problemMatrix [j][k] = 0;
}
}
}
/* After reading the input puzzle, call this function. This function
* goes through the problem matrix and calls the assignTag method that
* sets the proper tags to true.
*/
void fillTags (void) {
for (int i = 0; i < NUM; i++)
for (int j = 0; j < NUM; j++)
assignTag (i, j, problemMatrix[i][j]);
}
/* This function checks if the input value 'c' can be placed inside the
* problem matrix at the [i][j] position. The way this works is, the tags
* of the cells that are already filled are set to true. If the value 'c'
* is being written at a place [i][j] where it has no conflicts with the
* row, column or the block then it is valid and method returns true.
*/
bool checkValid (int i, int j, int c) {
c--;
if (tagRow[i][c] == true)
return false;
if (tagCol[c][j] == true)
return false;
if (tagBlk[(i/BLK)*BLK+j/BLK][c] == true)
return false;
return true;
}
/* This method is used to set the tags to true. Once it's determined that
* a value is valid (using the checkValid method, this method should be
* called. It will set the proper tags for the next checking.
*/
void assignTag (int i, int j, int n) {
if (n == 0)
return;
n--;
tagRow[i][n] = true;
tagCol[n][j] = true;
tagBlk[(i/BLK)*BLK+j/BLK][n] = true;
}
/* This method is used for the backtracking. Once the logical solving is
* done the class goes into backtracking mode. It sets a random valid value
* and tries to solve the puzzle. If it gives an error, the solver needs to
* go back (backtrack). This also means it needs to reset the tags which
* were set during the initial backtrack assumption.
*/
void resetTag (int i, int j, int n) {
if (n == 0)
return;
n--;
tagRow[i][n] = false;
tagCol[n][j] = false;
tagBlk[(i/BLK)*BLK+j/BLK][n] = false;
}
/* This method is just a placeholder for different solving mechanisms. The
* puzzles can have various difficulties and solver may need more methods.
* Those algorithms would be called through this method. Mainly for future
* use.
*/
bool solvePuzzle(void) {
solveLogical ();
//printPuzzle();
return solveBacktrack (0, 0, problemMatrix);
}
/* This method tries to solve the puzzle logically. It's a simple set of
* implication rules. It goes on checking in each block, row and then
* column to check if there are any singles (cells where only one value
* can be put). If it finds such cells then it assigns the value.
*
* The method is in an infinite loop. Until it does not have any value to
* assign to any cell it stays in the loop otherwise it breaks out.
*/
void solveLogical (void) {
int i, j, k, l = 0, row = 0, col = 0, cnt = 0;
bool flagNotSingle = false; // Used to check if the cell is indeed a singles cell.
bool flagValueSet = false; // Is set if we made an assignment in the while loop.
while (true) {
flagValueSet = false; // Assume we make no assignment.
for (k = 0; k < NUM; k++) { // Check all the 9 blocks for singles.
for (l = 1; l < (NUM+1); l++) {
cnt = 0;
flagNotSingle = false; // Assume we have no singles.
for (i = (k/COL)*COL; i < ((k/COL)*COL + COL); i++) {
for (j = (k%COL)*ROW; j < ((k%COL)*ROW + ROW); j++) {
if (problemMatrix [i][j] > 0) // Skip the cells that are already filled.
continue;
if (checkValid (i,j,l)) { // If empty cell found, check if current value is valid.
row = i;
col = j;
cnt ++;
}
if (cnt > 1) { // Make sure it was a singles value and not doubles or more.
flagNotSingle = true; // If more than one valid value was found, break.
break;
}
}
if (flagNotSingle) // More than one valid value found, break.
break;
}
if (cnt == 1) { // If any singles value was found then assign it.
problemMatrix [row][col] = l;
assignTag (row, col, l); // Then set tags.
flagValueSet = true; // Set the flag that assignment was made.
}
}
}
for (i = 0; i < NUM; i++) { // Check all columns.
for (l = 1; l < NUM; l++) {
cnt = 0;
for (j = 0; j < NUM; j++) {
if (problemMatrix [i][j] > 0) // Skip cells that are already filled.
continue;
if (checkValid (i, j, l)) { // If empty cell found, check if current value is valid.
row = i;
col = j;
cnt++;
}
if (cnt > 1) { // Make sure it was a singles value and not doubles or more.
flagNotSingle = true; // If more than one valid value was found, break.
break;
}
}
if (cnt == 1) { // If any singles value was found then assign it.
problemMatrix [row][col] = l;
assignTag (row, col, l); // Then set tags.
flagValueSet = true; // Set the flag that assignment was made.
}
}
}
for (i = 0; i < NUM; i++) { // Check all rows.
for (l = 1; l < NUM; l++) {
cnt = 0;
for (j = 0; j < NUM; j++) {
if (problemMatrix [j][i] > 0) // Skip cells that are already filled.
continue;
if (checkValid (j, i, l)) { // If empty cell found, check if current value is valid.
row = j;
col = i;
cnt++;
}
if (cnt > 1) { // Make sure it was a singles value and not doubles or more.
flagNotSingle = true; // If more than one valid value was found, break.
break;
}
}
if (cnt == 1) { // If any singles value was found then assign it.
problemMatrix [row][col] = l;
assignTag (row, col, l); // Then set tags.
flagValueSet = true; // Set the flag that assignment was made.
}
}
}
if(!flagValueSet) // If assignment was not made during an iteration, break out of logical solve.
break;
}
}
/* This method is called after the logical solver. This method can be
* directly called to solve the puzzles also but that has a problem.
*
* Some puzzles are designed such that backtrack solvers take a long
* time to solve them. (Google for more information). The logical solver
* removed some of the issues from that and makes solving faster.
*
* For simple puzzles, logical solve will give the result and this method
* will just exit on initial check.
*
* The method is simple, it is similar to logical solve but instead of
* checking if the value is singles or not, it only checks if the value
* is valid, if it is then the solver assumes that to be the correct value
* and advances, if it encounters an error, it goes back to last modified
* cell and checks for another valid value. If there is none it goes back
* another step and so on till all the cells are filled.
*/
bool solveBacktrack (int i, int j, int proMat [9][9]) {
if (i == NUM) { // This function goes checking row after row.
i = 0;
if (++j == NUM) // Once a row is finished, go to next row.
return true; // If final cell is reached, puzzle is solved.
}
if (proMat[i][j] > 0) // Skip filled cells
return solveBacktrack (i + 1, j, proMat); // Check next row of current column.
for (int val = 1; val <= NUM; val++) { // Empty cell found. Check from 1 to 9.
if (checkValid(i, j, val)) { // If it is legal (check description of legal) then fill the cell.
proMat[i][j] = val;
assignTag (i, j, val); // Also set the tags for checking next value.
if (solveBacktrack (i+1,j,proMat)) // And call the solve function again.
return true; // If it returns true that means the puzzle is solved.
else // If not then we need to reset the tags and backtrack.
resetTag (i, j, proMat[i][j]);
}
}
resetTag (i, j, proMat[i][j]); // Reset tags and backtrack.
proMat[i][j] = 0; // Also reset the value for next iteration.
return false;
}
/* This method is used to print the problem matrix to console. Mainly used
* for debugging purpose.
*/
void printPuzzle (void) {
cout << "-------------------------------------------------------" << endl;
for (int row = 0; row < NUM; row++) {
cout << "| ";
for (int col = 0; col < NUM; col++) {
cout << " *" << problemMatrix[row][col] << "* ";
if (!((col+1) % BLK))
cout << " | ";
}
if (!((row+1) % BLK))
cout << endl << "-------------------------------------------------------" << endl;
else
cout << endl;
}
}
};