| # |
Title |
Difficulty |
Topic |
| 37 |
Sudoku Solver |
Hard |
Hash Table; Backtracking |
Description
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9 must occur exactly once in each row.
- Each of the digits
1-9 must occur exactly once in each column.
- Each of the the digits
1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.
A sudoku puzzle…
…and its solution numbers marked in red.
Note:
- The given board contain only digits
1-9 and the character '.'.
- You may assume that the given Sudoku puzzle will have a single unique solution.
- The given board size is always
9x9.
Backtracking
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
|
class {
public void solveSudoku(char[][] board) {
if(board == null || board.length == 0 ||
board[0] == null || board[0].length == 0) return;
solve(board);
}
public boolean solve(char[][] board) {
for(int i=0; i<board.length; i++) {
for(int j=0; j<board[0].length; j++) {
if(board[i][j] == '.') {
for(char c='1'; c<='9'; c++) {
if(isValid(board, i, j, c)) {
board[i][j] = c;
if(solve(board)) return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
public boolean isValid(char[][] board, int row, int col, char c) {
for(int i=0; i<9; i++) {
if(board[row][i] != '.' && board[row][i] == c) return false;
if(board[i][col] != '.' && board[i][col] == c) return false;
if(board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
}
return true;
}
}
|
时间复杂度为$$O(9^M)$$，$$M$$表示空格的个数。
近期评论