-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathSudokuSolver.java
More file actions
69 lines (66 loc) · 2.1 KB
/
SudokuSolver.java
File metadata and controls
69 lines (66 loc) · 2.1 KB
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
public class Solution {
public String digits = "123456789";
public void solveSudoku(char[][] board) {
this.dfs(0, 0, board);
}
public boolean dfs(int i, int j, char[][] board) {
if (j == 9) {
if (i == 8) {
return true;
} else {
return this.dfs(i+1, 0, board);
}
}
if (board[i][j] != '.') {
return this.dfs(i, j+1, board);
} else {
for (int k = 0; k < 9; k++) {
board[i][j] = this.digits.charAt(k);
if (this.check(i, j, board) == false) {
board[i][j] = '.';
} else {
if (this.dfs(i, j+1, board) == true) {
return true;
} else {
board[i][j] = '.';
}
}
}
}
return false;
}
public boolean check(int i, int j, char[][] board) {
for (int m = 0; m < 9; m++) {
if (m != i && board[m][j] == board[i][j]) {
return false;
}
}
for (int m = 0; m < 9; m++) {
if (m != j && board[i][m] == board[i][j]) {
return false;
}
}
int tempm = i / 3 * 3;
int tempn = j / 3 * 3;
for (int m = tempm; m < tempm + 3; m++) {
for (int n = tempn; n < tempn + 3; n++) {
if (i != m && j != n && board[m][n] == board[i][j]) {
return false;
}
}
}
return true;
}
public static void main (String args[]) {
Solution sol = new Solution();
String[] boards = {"..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."};
char[][] board = new char[9][9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
board[i][j] = boards[i].charAt(j);
}
}
sol.solveSudoku(board);
System.out.println(board[0][0]);
}
}