LeetCode 37. 解数独
- 题目:37. 解数独
编写一个程序,通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则:
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。
一个数独。
答案被标成红色。
-
Note:
给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。 -
思路
难点:
检查块这里难理解,解释见注释
if(board[3*(row/3)+i/3][3*(col/3)+i%3]==c)
return false;
public class SolveSudoku {
public void solveSudoku(char[][] board) {
if(board==null||board.length==0)
return;
solve(board);
}
private boolean solve(char[][] board) {
for (int i=0;i<board.length;i++){
for (int j=0;j<board[0].length;j++){
//遍历每一个ceil,如果ceil的值是'.',则给ceil赋值1-9,看是否能得到解
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;
else
board[i][j]='.';////回退
}
}
//给(i,j)位置赋值1-9都不满足题意,则证明前一步的赋值不能得到正确的解,
// 则返回循环的上一步,走if(solve(board))的else分支,即令board[i][j]='.',进行赋值的回退
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int row, int col, char c) {
for (int i=0;i<9;i++){
//检查列
if(board[row][i]==c)
return false;
//检查行
if(board[i][col]==c)
return false;
/*
检查块:这里难理解,可以画图
例如row=3,col=4
i=0 1 2 3 4 5 6 7 8
计算出要检查的board行和列的值:
r=3 3 3 4 4 4 5 5 5
c=0 1 2 0 1 2 0 1 2
* */
if(board[3*(row/3)+i/3][3*(col/3)+i%3]==c)
return false;
}
return true;
}
}