回溯算法最佳实践：解数独 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：回溯算法最佳实践：解数独

评论礼仪 见这里，违者直接拉黑。

[xiaoye-2018]

auto.js不错

[typedefstruct32]

这道题我一开始写成了如下的回溯，发现最后返回的board是和输入的一样。我理解是回溯过程中没有及时退出，将原本”有解的board“又一步步还原成了”原始board“，各位大佬看下我的分析对吗。（去掉注释以后的代码可以正确运行）

    void dfs(vector<vector<char>>& board, int x, int y) {
        if (x == 9) {
           // ans = board;    //这里需要用ans来保存中间成功的结果，否则会在dfs回溯中被清成'.'
           //flag = true;
           return;
        }
        if (y == 9) {
            dfs(board, x + 1, 0);
            return;
        }
        if (board[x][y] != '.') {
            dfs(board, x, y + 1);
            return;
        }
        for (char i = '1'; i <= '9'; i++) {
            if (valid(board, x, y, i)) {
                board[x][y] = i;
                dfs(board, x, y + 1);   //要么写成if (dfs(...)) return true;的形式，要么用ans来保存成功时board的状态。否则会在回溯过程，board变为原来的样子
                //if (flag) return;
                board[x][y] = '.';
            }
        }
        return;
    }

[dotJunz]

你的分析没问题吧，一般这种找到一种解就结束的回溯算法，它的返回值都是布尔类型。

返回布尔类型和你用ans来保存成功时board的状态，本质是一样的吧。
if (dfs(...)) return true; 和 if (flag) return; 这两条语句的作用不都是在找到一个解的时候防止执行 board[x][y] = '.'; 吗？
如果没有这两条语句，不就又回溯成初始状态了吗？

另一种理解：回溯算法在不加限制的情况下，会把所有可能走一遍，然后回到初始状态。有的题目我们希望算法在某一个状态终止，就用布尔返回值来终止（更常用一些），或者你用ans保存也行。

[bert82503]

打卡，感谢！

[muenzhang]

@typedefstruct32 你的想法是对的，一般我在写的时候都是在类里写一个变量，然后算出一个结果就把他加进去，如果只是单纯回溯的话一定会变回最开始的样子，因为每次修改后都会把它改回去

[LebronHarden1]

请问周围一圈的位置判断公式怎么得出的

[cheng-miao]

1

[ystanzhang]

Subbox 这段代码

if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
            return false;

如何找【4，6】的subbox
图文理解跟容易：https://pasteboard.co/fyW9xjeDA6fH.png

[Hyuvo]

感谢老哥！

[liang734]

class Solution {
    // 回溯法
    public void solveSudoku(char[][] board) {
        backTraverse(board,0,0);
    }  

    public boolean backTraverse(char[][] board,int i,int j){
        int m = board.length;
        int n = board[0].length;
        // 递归完一列，则换下一行
        if(j == n){
            return backTraverse(board,i + 1,0);
        }

        // 递归完所有行
        if(i == m){
            return true;
        }

        // 当前位置已经有数字则填下一个位置
        if(board[i][j] != '.'){
            return backTraverse(board,i,j + 1);
        }

        for(char c = '1';c <= '9';c++){
            if(!isValid(board,i,j,c)){
                continue;
            }
            // 选择
            board[i][j] = c;
            if(backTraverse(board,i,j + 1)){
                return true;
            }
            // 撤销选择
            board[i][j] = '.';
        }
        return false;
    }

    // 判断board[i][j] 位置是否可以放置 c
    public boolean isValid(char[][] board,int i,int j,char c){
        int m = board.length;
        int n = board[0].length;
        for(int k = 0;k < n;k++){
            if(board[i][k] == c)
                return false;
        }
        for(int k = 0;k < m;k++){
            if(board[k][j] == c)
                return false;
        }
 
        for(int k = i / 3 * 3;k <= i / 3 * 3 + 2;k++){
            for(int l = j / 3 * 3;l <= j / 3 * 3 + 2;l++){
                if(board[k][l] == c){
                    return false;
                }
            }
        }
        return true;
    }
}

[dotJunz]

判断3x3小方框的逻辑更好懂一些👍

[wztsir]

这个脚本是怎么启动运行的呢

[wztsir]

解决了，但好像，用处不大，不过这个auto.js确实牛啊！！

[zangxycoding]

判断 3 x 3 方框的逻辑也太抽象了。。

[marcmk6]

感觉如果遵循尽可能让选择空间小的原则，从可选数字最少的位置开始做回溯，也许比逐行从左到右填要快。就是实现起来可能非常复杂，需要维护一个空格子组成的优先队列：每个格子的优先级是填入之后不会违反规则的数字的个数，越小越优先。
然后本题就变成了数据结构设计题(逃

[pixel-revolve]

您好，我有用这样的思路完成本题，但最后出现了超时问题，而且本人能力还无法解决😭，现在的代码过测试用例的时候会直接卡住。而如果我将traversal返回true的条件改成k==problemTotal-1的时候有输出只是和结果还差几步，说明程序本身在一定程度上正确的运行着。

/*
 * @lc app=leetcode.cn id=37 lang=cpp
 *
 * [37] 解数独
 */
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
// @lc code=start
bool cmp(vector<int>& a1,vector<int>&a2){
    if(a1[2]>a2[2]){
        return false;
    }
    return true;
}
class Solution {
public:
    vector<int> all9={1,2,3,4,5,6,7,8,9};
    int problemTotal=0;
    void solveSudoku(vector<vector<char>>& board) {
        vector<set<int>> col(9);
        vector<set<int>> lev(9);
        vector<set<int>> block(9);
        vector<vector<int>> threeArr;

        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if(board[i][j]!='.'){
                    col[j].insert(board[i][j]-'0');
                    lev[i].insert(board[i][j]-'0');
                    block[(i/3)*3+j/3].insert(board[i][j]-'0');
                }
            }
        }

        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if(board[i][j]=='.'){
                    vector<int> res1;
                    set_union(lev[i].begin(),lev[i].end(),col[j].begin(),col[j].end(),inserter(res1,res1.begin()));    
                    vector<int> res2;
                    set_union(res1.begin(),res1.end(),block[(i/3)*3+j/3].begin(),block[(i/3)*3+j/3].end(),inserter(res2,res2.begin()));    
                    res1.clear();
                    set_difference(all9.begin(),all9.end(),res2.begin(),res2.end(),inserter(res1,res1.begin()));
                    vector<int> three;
                    three.push_back(i);
                    three.push_back(j);
                    three.push_back(res1.size());
                    threeArr.push_back(three);
                    problemTotal++;
                }
            }
        }

        sort(threeArr.begin(),threeArr.end(),cmp);
        
        traversal(board,0,col,lev,block,threeArr);
    }

    bool traversal(vector<vector<char>>& board,int k,
    vector<set<int>> col, vector<set<int>> lev,vector<set<int>> block,
    vector<vector<int>> threeArr){
        if(k==problemTotal){//没有要解决的问题了
            return true;
        }

        for (int i = k; i < problemTotal; i++)
        {
            vector<int> three=threeArr[i];
            vector<int> res1;
            set_union(lev[three[0]].begin(),lev[three[0]].end(),col[three[1]].begin(),col[three[1]].end(),inserter(res1,res1.begin()));    
            vector<int> res2;
            set_union(res1.begin(),res1.end(),block[(three[0]/3)*3+three[1]/3].begin(),block[(three[0]/3)*3+three[1]/3].end(),inserter(res2,res2.begin()));    
            res1.clear();
            set_difference(all9.begin(),all9.end(),res2.begin(),res2.end(),inserter(res1,res1.begin()));
            if(res1.size()<1)//当前位置没数可以选了
                return false;
            for (auto &&num : res1)
            {
                board[three[0]][three[1]]=num+'0';
                lev[three[0]].insert(num);
                col[three[1]].insert(num);
                block[(three[0]/3)*3+three[1]/3].insert(num);
                if(traversal(board,k+1,col,lev,block,threeArr))
                    return true;
                lev[three[0]].erase(num);
                col[three[1]].erase(num);
                block[(three[0]/3)*3+three[1]/3].erase(num);
                board[three[0]][three[1]]='.';
            }
        }
        return false;
    }
};
// @lc code=end
int main(){
    vector<vector<char>> board={{'5','3','.','.','7','.','.','.','.'},{'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},{'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}};
    Solution sol;
    sol.solveSudoku(board);
    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board[i].size(); j++)
        {
            cout<<board[i][j]<<" ";
        }
        cout<<endl;
    }
    return 1;
}

[diandengpao]

看不太懂，可以说下你这个思路和普通的有什么区别吗

[pixel-revolve]

就是遵循了人类做数独问题的思考方式，从尽可能选择少的位置开始做回溯。代码这里是做了一个三元组threeArr，记录每个位置可以选择的数字数量，然后排序。最后在这个三元组上回溯。越上层的递归的入口少的话，理论上来说应该可以更快的找到最后的唯一解。

[diandengpao]

好吧，还是不太懂，但是照理来讲只要你能证明每个位置的选择是合法的，那么位置的枚举顺序应该是无关的。
但如果还是错的话，那就是排序的问题了，也就是跟位置的枚举顺序有关。

[xinyuG]

东哥您好，请问为什么这两个判断的后面要加return，期待您的解答，谢谢🙏

    if (j == n) {
        // 穷举到最后一列的话就换到下一行重新开始。
        backtrack(board, i + 1, 0);
        return;
    }
    
    // 如果该位置是预设的数字，不用我们操心
    if (board[i][j] != '.') {
        backtrack(board, i, j + 1);
        return;
    } 

[diandengpao]

从代码上来讲 不return的话 执行完j == n的递归还会再接着执行 != '.'的递归。
从逻辑上来讲，带有返回值的递归可以看成子树，即backtrack(board, i + 1, 0)和backtrack(board, i, j + 1)是两颗都会到达底部的子树，那么这两颗到达底部的子树如果为假，即当前节点为假。

[bruceeewong]

好酷啊，学了算法可以做游戏外挂，又有动力刷题了！
关于那个抽象的3x3 grid 公式 board[(r/3)*3 + i/3][(c/3)*3 + i%3]，拆解一下就是：

• (r/3)*3 & (c/3)*3 求的是行和列的偏移量，对于r和c来说，是3的几倍就偏移几倍的3格 (注意整型除法会先向下取整）
• 因为 i=0 -> 8， 所以 i / 3 在每一次循环的变化是 0, 0, 0, 1, 1, 1, 2, 2, 2
• 因为 i=0 -> 8， 所以 i % 3 在每一次循环的变化是 0, 1, 2, 0, 1, 2, 0, 1, 2

我画了两种情况的图，终于搞懂了，求的并不是以[r,c]为中心的3x3 grid，而是行列数对齐3的倍数的grid，但是完全符合要求：
当要判断 r=1, c=1 周围的3x3grid时：

当要判断 r=4, c=2 周围的3x3grid时：

[labuladong]

👍

[z0z0r4]

这个不错

[leihehehe]

不写成boolean返回值也可以，就是需要一个boolean variable。
这道题使用回溯算法，遇到不对的答案，把棋盘恢复成.，然后重新尝试其他选项。因为题目要求返回原来的棋盘数组，所以我们不希望当解出答案后，棋盘再被恢复。
我能想到的有以下几种方法：

1. 可以新建数组再重新for循环赋值给原数组回来（复杂度太高）
2. 可以使用boolean backtrack()的方式
3. 可以使用一个外部的boolean变量来控制。
   下面是第三种方法的代码：

public void solveSudoku(char[][] board) {
        backtrack(board,0,0);
    }
    boolean solved = false;
    public void backtrack(char[][] board, int i, int j){
        int row = 9, col = 9;
        if(j==col){
            backtrack(board,i+1,0);
            return;
        }
        if(i==row){
            //达到最后一行，说明已经解出答案
            solved=true;
            return;
        }
        if(board[i][j]!='.'){
            backtrack(board,i,j+1);
            return;
        } 
        for(char c = '1';c<='9';c++){
            if(!isValid(board,i,j,c)) continue;
            board[i][j]=c;
            backtrack(board,i,j+1);
            // 如果这个问题已经被解决了，我们不应该把board还原成`.`
            if(solved) break;
            board[i][j]='.';
        }
    }

    public boolean isValid(char[][] board, int i ,int j, int target){
        for(int row = 0;row<board.length;row++){
            if(board[row][j]==target) return false;
        }
        for(int col = 0;col<board[0].length;col++){
            if(board[i][col]==target) return false;
        }
        int startRow = (i/3)*3;
        int startCol = (j/3)*3;
        for(int row = startRow;row<startRow+3;row++){
            for(int col = startCol;col<startCol+3;col++){
                if(board[row][col]==target) return false;
            }
        }
        return true;
    }

[zenyanggongmian1995]

  public void solveSudoku(char[][] board) {
    backtrack(board, 0, 0);
  }

  boolean backtrack(char[][] board, int row, int col) {
    int size = 9;

    if (col == size) {
      // 穷举到最后一列的话就换到下一行重新开始。
      return backtrack(board, row + 1, 0);
    }

    if (row == size) {
      // row变成9，说明找完了整个棋盘，只要整个流程走通，就说明找到了一个可行解，触发 base case
      return true;
    }

    if (board[row][col] != '.') {
      // 如果有预设数字，不用我们穷举
      return backtrack(board, row, col + 1);
    }

    for (char ch = '1'; ch <= '9'; ch++) {
      // 如果遇到不合法的数字，就跳过
      if (!isValid(board, row, col, ch)) {
        continue;
      }

      board[row][col] = ch;
      // 如果找到一个可行解，立即结束
      if (backtrack(board, row, col + 1)) {
        return true;
      }
      board[row][col] = '.';
    }
    // 穷举完 第1列到第9列，依然没有找到可行解，此路不通
    return false;
  }

  // 判断 board[row][col] 是否可以填入字符 ch
  boolean isValid(char[][] board, int row, int col, char ch) {
    int size = 9;
    for (int i = 0; i < size; i++) {
      // 判断行是否存在重复
      if (board[row][i] == ch) {
        return false;
      }
      // 判断列是否存在重复
      if (board[i][col] == ch) {
        return false;
      }
      // 判断 3 x 3 方框是否存在重复
      
      // 一般来说，判断他所在的3*3方格是否合法，需要找到自己所属于那个3*3的格子的左上角元素位置（下面就是这么做的），然后使用双重for循环遍历这9个格子去判断有没有重复。
      // 这里具体实现就是使用偏移量管理，3 * (row / 3)，3 * (col / 3) 找到了自己所属的3*3的格子的左上角元素位置，
      // 然后i的变化就是在控制遍历以3 * (row / 3)，3 * (col / 3) 为左上角顶点的方框中的不同元素。
      // 至于 i/3和 i%3 , 这个其实就是使用一维坐标访问二维数组， i/row.size = 行号，i%row.size = 列号。
      // 二者组合。
      int boxRow = 3 * (row / 3) + i / 3;
      int boxCol = 3 * (col / 3) + i % 3;
      if (board[boxRow][boxCol] == ch) {
        return false;
      }
    }
    return true;
  }

[diandengpao]

// 判断行是否存在重复
if (board[row][i] == ch) {
return false;
}
不应该是判断列吗