-
Notifications
You must be signed in to change notification settings - Fork 0
/
SudokuSolver.java
193 lines (155 loc) · 5.83 KB
/
SudokuSolver.java
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
// Sudoku Project
// November 2017
// Andy Vainauskas
// Reference: http://www.geeksforgeeks.org/backtracking-set-7-suduku/
// Reference: http://codefordummies.blogspot.com/2014/01/backtracking-solve-sudoku-in-java.html
//
// SudokuSolver uses the backtracking algorithm to solve a 9x9 Sudoku grid.
//
public class SudokuSolver {
static int N = 9;
static int grid[][];
// Class to abstract the representation of a cell
// Cell = (x, y)
static class Cell {
int row, col;
public Cell(int row, int col) {
super();
this.row = row;
this.col = col;
}
@Override
public String toString() {
return "Cell [row=" + row + ", col=" + col + "]";
}
}
SudokuSolver(int[][] grid) {
this.grid = grid;
}
public static int[][] getGrid() {
return grid;
}
// Method that checks if a Cell is valid
static boolean isValid(Cell cell, int value) {
// Throws an error since a cell that is not empty is assumed to be already valid if
// it was generated by the SudokuGenerator
if (grid[cell.row][cell.col] != 0) {
throw new RuntimeException(
"Cannot check if isValid for a cell that already has a value");
}
// If value present row, return false
for (int c = 0; c < 9; c++) {
if (grid[cell.row][c] == value)
return false;
}
// If value present in col, return false
for (int r = 0; r < 9; r++) {
if (grid[r][cell.col] == value)
return false;
}
// If value present in grid, return false
// To find the 3x3 sub-grid, calculate (x1,y1) (x2,y2)
int x1 = 3 * (cell.row / 3);
int y1 = 3 * (cell.col / 3);
int x2 = x1 + 2;
int y2 = y1 + 2;
for (int x = x1; x <= x2; x++)
for (int y = y1; y <= y2; y++)
if (grid[x][y] == value)
return false;
// If value not present in row, col and 3x3 sub-grid, return true
return true;
}
// Returns the next Cell, ensuring the algorithm does not extend past the 9x9 grid
static Cell getNextCell(Cell cur) {
int row = cur.row;
int col = cur.col;
// Next cell => col++
col++;
// If col > 8, then col = 0, row++ (reached end of row, got to next row)
if (col > 8) {
// goto next line
col = 0;
row++;
}
// Reached end of matrix, return null
if (row > 8)
return null;
Cell next = new Cell(row, col);
return next;
}
// Checks if the puzzle that the user entered is valid
static boolean isValidPuzzle() {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
Cell cell = new Cell(i, j);
if (grid[i][j] != 0) {
boolean invalid = hasError(cell, grid[i][j]);
if (invalid)
return false;
}
}
}
return true;
}
// Used by isValidPuzzle to check if a value entered already exists in the row, col, or 3x3 sub-grid
static boolean hasError(Cell cell, int value) {
// If value present row, return false
for (int c = 0; c < 9; c++) {
if (grid[c][cell.row] == value && cell.col != c)
return true;
}
// If value present in col, return false
for (int r = 0; r < 9; r++) {
if (grid[cell.col][r] == value && cell.row != r)
return true;
}
// If value present in grid, return false
// To find the 3x3 sub-grid, calculate (x1,y1) (x2,y2)
int x1 = 3 * (cell.row / 3);
int y1 = 3 * (cell.col / 3);
int x2 = x1 + 2;
int y2 = y1 + 2;
for (int x = x1; x <= x2; x++)
for (int y = y1; y <= y2; y++)
if (grid[x][y] == value && cell.row != x && cell.col != y)
return true;
// If value not present in row, col and 3x3 sub-grid, return true
return false;
}
// Implements the backtracking algorithm recursively
// Returns true if puzzle can be solved, false if it cannot
static boolean solve(Cell cur) {
// If the cell is null, we have reached the end
if (cur == null)
return true;
// If grid[cur] already has a value, there is nothing to solve, continue to next cell
if (grid[cur.row][cur.col] != 0)
// return whatever is being returned by solve(next)
// i.e the state of soduku's solution is not being determined by
// this cell, but by other cells
return solve(getNextCell(cur));
// This is where each possible value is being assigned to the cell,
// and checked if it is a solution or not.
// If grid[cur] doesn't have a value, try each possible value
for (int i = 1; i <= 9; i++) {
// Check if valid, if valid, then update
boolean valid = isValid(cur, i);
if (!valid) // i not valid for this cell, try other values
continue;
// Assign here
grid[cur.row][cur.col] = i;
// Continue with next cell
boolean solved = solve(getNextCell(cur));
// If solved, return, else try other values
if (solved)
return true;
else
grid[cur.row][cur.col] = 0; // reset
}
// If you reach here, then no value from 1 - 9 for this cell can solve the puzzle,
// so we must go back to a previously edited cell and check other values to see if
// they are also valid (one cell can initially have multiple valid values.
return false;
}
}