解数独

回溯法的应用-数独游戏

在开始进行回溯法解数独的之前，先来一道热身题，如果辨别是否是一个有效的数独。

数独游戏的规则是：

• 数字1-9在每一行只能出现一次。
• 数字1-9在每一列只能出现一次。
• 数字1-9在每一列以粗实线分隔的3x3宫内只能出现一次

由于题目比较简单，直接上代码

class Solution{
  public boolean isValidSudoku(char[][]board){
    //标记某一行的某一个数是否已经摆放
     boolean[][]row=new boolean[9][9];
    //标记某一列的某一个数是否已经摆放
    boolean[][]col=new boolean[9][9];
    //标记某一个块的某一个数是否已经摆放
    boolean[][]block=new boolean[9][9];
    for(int i=0;i<9;i++){
      for(int j=0;j<9;j++){
        if(board[i][j]!='.'){
          int num=board[i][j]-'1';
          //i决定一组block的起始位置，且block是3行，所以i/3 又因为每组block有3个，然后乘3
          //block为3列，所以j/3
          int blockIndex=i/3*3+j/3;
          if(row[i][num]||col[j][num]||block[blockIndex][num]) return false;
          else{
            row[i][num]=true;
            col[j][num]=true;
            block[blockIndex][num]=true;
            
        }
        }
      }
    }
    return true;
  }
}

有了上面对数独游戏的理解，接下来我们来进行完成解数独。

LeetCode 37、https://leetcode-cn.com/problems/sudoku-solver/

题目的意思非常明确，给我们一个9x9的方格，然后根据已经填充的部分来解决数独问题。

在之前的全排列问题，或者八皇后问题中。我详细介绍了回溯算法的具体思路，其实回溯算法就是一个暴力穷举的过程。而本题就非常适合于暴力穷举，因为我们要枚举所有的数字，只用稍加剪枝即可。

//对board进行穷举
void backtrack(char[][]board,int i,int j){
     for(char ch='1';ch<=9;ch++){
       //做选择
           board[i][j]=ch;
       //对下一个格子进行穷举
        backtrack(board,i,j+1);
       //回溯
       board[i][j]='.';
     }
}

但是很明显，我们在作出选择的情况下应该有一个先决条件，即并不是所有的1-9都是可以取到的.

//判断当前位置是否可以摆放
private boolean isValid(char[][]board,int r,int c,char ch){
    for(int i=0;i<9;i++){
      //对行进行判断
       if(board[r][i]==ch) return false;
      //对列进行判断
      if(board[i][c]==ch) return false;
      //对块进行判断
      if(board[(r/3)*3+i/3][(c/3)*3+i%3]) return false;
    }
  return true;
  
}

到这里，是不是我们还差一个所谓的basecase 即终止条件？

//表示某一列已经摆放完，接着从下一列的第一个元素开始摆放
if(j==9) return backtrack(board,i+1,0);
//触发basecase
if(i==9) return true;

接下来合并所有代码

class Solution {
    public void solveSudoku(char[][] board) {
        backtrack(board,0,0);
    }
    private boolean backtrack(char[][]board,int x,int y){
        if(y==9) return backtrack(board,x+1,0);
        if(x==9) return true;
      //当前格子不需要摆放
        if(board[x][y]!='.') return backtrack(board,x,y+1);
        for(char ch='1';ch<='9';ch++){
            if(!isValid(board,x,y,ch))continue;
            
            board[x][y]=ch;
            if(backtrack(board,x,y+1)) return true;
            board[x][y]='.';
        }
        return false;
    }
    private boolean isValid(char[][]board,int r,int c,char ch){
        for(int i=0;i<9;i++){
            //对行进行判断
            if(board[r][i]==ch) return false;
            //对列进行判断
            if(board[i][c]==ch) return false;
            //对块进行判断
            if(board[(r/3)*3+i/3][(c/3)*3+i%3]==ch) return false;
           
        }
         return true;
        
    }
}

总结 ：

• 回溯法就是如此的暴力，在我们需要枚举多个变量时，往往使用回溯法。
• 例如八皇后问题，实质上也是一个解数独问题，例如全排列问题，实际上也是对决策树进行遍历的过程。

赏

谢谢你请我喝奶茶

微信