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 93x3
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
.
判断当前插入的值有没有错误,没有继续填下面的
class Solution {//剪枝 mytip
public void solveSudoku(char[][] board) {
if(null==board ||0==board.length)
return;
help(board);
}
private boolean help(char[][] board){
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board.length; col++) {
if('.'==board[row][col]){
for (char i = '1'; i <= '9'; i++) {
if(isValidSudoku(board,row,col,i)){
board[row][col]=i;
if(help(board)){
return true;
}
else{
board[row][col]='.';
}
}
}
return false;
}
}
}
return true;
}
private boolean isValidSudoku(char[][] board,int row,int col,char ch) {
for (int i = 0; i <board.length ; i++) {
if(ch==board[row][i]||ch==board[i][col]){
return false;
}
}
int r = row/3*3;
int c = col/3*3;
for (int i = r; i <r+3 ; i++) {
for (int j = c; j < c+3 ; j++) {
if(ch==board[i][j]){
return false;
}
}
} return true;
}
}
另外可以通过以下方式加速
- 从选项少的格子开始
- 先使用n*n的循环,查找所有空格的可选数,根据可选数排序,从可选数少的开始填写
- 用Dancing Links http://www.cnblogs.com/grenet/p/3145800.html https://www.cnblogs.com/grenet/p/3163550.html
相关题
有效的数独 LeetCode36 https://www.cnblogs.com/zhacai/p/10622779.html