LeetCode-37.Sudok Solver

时间:2025-03-15 19:06:25

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. 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 '.'.

LeetCode-37.Sudok Solver
A sudoku puzzle...

LeetCode-37.Sudok Solver
...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;
}
}

另外可以通过以下方式加速

相关题

有效的数独 LeetCode36 https://www.cnblogs.com/zhacai/p/10622779.html