题目:
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'
.
You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
链接: http://leetcode.com/problems/sudoku-solver/
题解:
新加坡总理李显龙也做过的一题,还是用C做的,各种比特运算,巨快。思路就是DFS + Backtracking。在哪里回溯,怎样更好的构建DFS,需要多加练习。Knuth提到还有一种Dancing Links方法,用来构造回溯的,还不知道怎样使用。以及Boltzmann Machine。
Time Complexity - O(9m), Space Complexity - O(m), m是'.'的数目。
public class Solution {
public void solveSudoku(char[][] board) {
if(board == null || board.length == 0)
return;
trySolveSudokuDFS(board);
} private boolean trySolveSudokuDFS(char[][] board) {
for(int row = 0; row < 9; row++) {
for(int col = 0; col < 9; col++) {
if(board[row][col] == '.') {
for(char num = '1'; num <= '9'; num++) {
if(isValid(board, row, col, num)) {
board[row][col] = num;
if(trySolveSudokuDFS(board)) //DFS
return true;
else
board[row][col] = '.'; //back-tracking
}
}
return false;
}
}
} return true;
} private boolean isValid(char[][] board, int row, int col, char c) {
for(int i = 0; i < 9; i++) //check if current col valid
if(board[i][col] == c)
return false; for(int j = 0; j < 9; j++) //check if current row valid
if(board[row][j] == c)
return false; for(int i = row / 3 * 3; i < row / 3 * 3 + 3; i++) { //check if current block valid
for(int j = col / 3 * 3; j < col / 3 * 3 + 3 ; j++) {
if(board[i][j] == c)
return false;
}
} return true;
}
}
二刷:
根一刷使用的方法一样。主要还是DFS+ Backtracking。这里需要重新建立一个boolean类型的method canSolveSudoku,然后根据这个method来进行DFS。每次DFS之前,我们要先对'.'的位置进行预判断,检查是否能够放置从‘1’ - ‘9’的字符,假如可以,则我们设定这个位置的字符,之后进行DFS。否则我们尝试下一个字符。当DFS失败的时候,我们要backtracking,把这个位置的值重新设置为'.'。由于这个method canSolveSudoku是对于整个矩阵进行的dfs,所以在if block结束的时候我们就可以知道是否存在这样一个解, 我们可以在这里放一个 return false来提前终止循环,因为所有的条件我们都已经判断过了。
这里dfs的time complexity, braching factor是9 ,深度是'.'的个数m,所以时间复杂度是O(9m),空间复杂度是O(9m) = O(m)。
Time Complexity - O(9m), Space Complexity - O(m)
Java:
public class Solution {
public void solveSudoku(char[][] board) {
canSolveSudoku(board);
} private boolean canSolveSudoku(char[][] board) {
if (board == null || board.length == 0) {
return false;
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
if (board[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (isCurrentBoardValid(board, i, j, c)) {
board[i][j] = c;
if (canSolveSudoku(board)) {
return true;
} else {
board[i][j] = '.'; // backtracking
}
}
}
return false;
}
}
}
return true;
} private boolean isCurrentBoardValid(char[][] board, int row, int col, char c) {
for (int i = 0; i < board.length; i++) {
if (board[i][col] == c) {
return false;
}
} for (int j = 0; j < board[0].length; j++) {
if (board[row][j] == c) {
return false;
}
} for (int i = row / 3 * 3; i < row / 3 * 3 + 3; i++) {
for (int j = col / 3 * 3; j < col /3 * 3 + 3; j++) {
if (board[i][j] == c) {
return false;
}
}
}
return true;
}
}
Reference:
https://en.wikipedia.org/wiki/Dancing_Links
http://www.csc.kth.se/utbildning/kth/kurser/DD143X/dkand12/Group6Alexander/final/Patrik_Berggren_David_Nilsson.report.pdf
https://leetcode.com/discuss/30482/straight-forward-java-solution-using-backtracking