回溯算法最佳实践：解数独 :: 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;
    }

[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