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
|
/**
* Sudoku solver (exploration + backtracking)
*
* @author Xavier PHILIPPEAU
*/
public class SudokuSolver {
// Sudoku size K=square size, N=grid size (N=K*K)
private final int K, N;
// the grid to solve
private int[][] solution;
// marker for the initial (fixed) values
private boolean[][] fixed;
// locks on the rows, columns and squares
private boolean[][] lockrow, lockcol, locksqr;
// constructor
public SudokuSolver(int K) {
this.K = K;
this.N = K*K;
}
// initialize/reset structures
private void initialize() {
this.solution = new int[N][N];
this.fixed = new boolean[N][N];
this.lockrow = new boolean[N][N];
this.lockcol = new boolean[N][N];
this.locksqr = new boolean[N][N];
}
// load initial grid
private void load(String grid) {
for(int i=0;i<grid.length();i++) {
char c = grid.charAt(i);
int row = i/N, col = i%N, val = c-'0';
if (c=='.') continue;
solution[row][col]=val;
fixed[row][col]=true;
setlock(row,col,val, true);
}
}
// set/unset locks for the tuple (row,col,value)
private void setlock(int row, int col, int val, boolean state) {
int sqr=(col/this.K)+this.K*(row/this.K);
this.lockrow[row][val-1]=state;
this.lockcol[col][val-1]=state;
this.locksqr[sqr][val-1]=state;
}
// check if a tuple (row,col,value) is locked
private boolean islocked(int row, int col, int val) {
if (this.lockrow[row][val-1]) return true;
if (this.lockcol[col][val-1]) return true;
int sqr=(col/this.K)+this.K*(row/this.K);
if (this.locksqr[sqr][val-1]) return true;
return false;
}
// print grid
private void print() {
StringBuffer sb = new StringBuffer();
for(int r=0;r<N;r++) {
for(int c=0;c<N;c++)
sb.append( (solution[r][c]==0)?".":solution[r][c] ).append(" ");
sb.append("\n");
}
System.out.println(sb.toString());
}
// solver
public void solve(String grid) {
// init structures
initialize();
// load and print initial grid
load(grid);
print();
boolean backtrack=false;
int position=0;
// complete tree exploration with backtracking
while(position>=0 && position<N*N) {
int row = position/N;
int col = position%N;
// fixed cell : skip and continue
if (fixed[row][col]) {
if (backtrack) position--; else position++;
continue;
}
// remove the previous lock (if any)
if (solution[row][col]>0) setlock(row,col,solution[row][col], false);
// lookup for a possible value
int val = solution[row][col]+1;
while(val<=N && islocked(row,col,val)) val++;
if (val<=N) {
// value found: add to current solution
solution[row][col]=val;
// set the lock
setlock(row,col,val, true);
// go next
backtrack=false;
position++;
} else {
// no value found: backtrack
solution[row][col]=0;
// go previous
backtrack=true;
position--;
}
// end loop
}
// exited the loop while backtracking => no solution.
if (position<0) {
System.out.println("no solution");
return;
}
// else it'ok => print solution.
print();
}
} |
