力扣每日一题37：解数独

题目

大致思路

方法一：回溯剪枝（正常人能想出来的）

方法二：位运算优化剪枝

需要使用的位运算技巧

代码

位运算怎么就优化了呢？

方法三：枚举优化。

官解代码

方法四：舞蹈链算法

题目

困难

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：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"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

面试中遇到过这道题?

1/5

是

否

通过次数

248.8K

提交次数

367.3K

通过率

67.7%

大致思路

使用一个数据记录每个每一行，每一列，每一个3*3宫格中数组1-9出现的情况。

对所有空格（也就是需要填数的地方）进行遍历填数，判断这个位置能填1-9中的哪个数字，如果数字num在空格所在的行、列、3*3宫格都没出现过，那就可以把num放进去，然后填写下一个空格。当填写完最后一个空格的时候，就代表解完了。

方法一：回溯剪枝（正常人能想出来的）

对于每一行、每一列、每个3*3宫格中1-9出现的情况，我们都用一个哈希表表示。

这样在对某个空格进行填数num时，我们只需要判断这个空格所在行、所在列、所在3*3宫格有没有出现过num即可。

class Solution {
public:
    //判断九行、九列、九个格中数字1-9有无出现的哈希表
    int rows[9][9];
    int columns[9][9];
    int boxes[3][3][9];

    vector<pair<int,int>> blanks;//需要填写的空格

    bool flag;//用来剪枝
    void solveSudoku(vector<vector<char>>& board) {
        //初始化哈希表
        memset(rows,0,sizeof(rows));
        memset(columns,0,sizeof(columns));
        memset(boxes,0,sizeof(boxes));
        flag=false;
        
        //遍历一次9*9宫，寻找空格并更新哈希表
        int i,j;
        for(i=0;i<9;i++)
        {
            for(j=0;j<9;j++)
            {
                char c=board[i][j];
                if(c=='.'){
                    blanks.emplace_back(i,j);//blanks.emplace_back({i,j});会有语法错误
                }else{
                    int digit=c-'0';
                    rows[i][digit-1]=columns[j][digit-1]=boxes[i/3][j/3][digit-1]=1;
                }
            }
        }
        backtrack(board,0);
    }
    void backtrack(vector<vector<char>>& board,int index){
        //填完了最后一个空格，
        if(index==blanks.size()){
            flag=true;
            return;
        }
        //1-9遍历
        int x=blanks[index].first;
        int y=blanks[index].second;
        for(int num=1;num<=9&&flag==false;num++){
            if(rows[x][num-1]==0&&columns[y][num-1]==0&&boxes[x/3][y/3][num-1]==0){
                rows[x][num-1]=columns[y][num-1]=boxes[x/3][y/3][num-1]=1;
                board[x][y]=num+'0';
                backtrack(board,index+1);
                rows[x][num-1]=columns[y][num-1]=boxes[x/3][y/3][num-1]=0;
            }
        }
    }
};

方法二：位运算优化剪枝

看了题解我才知道这也能优化…………

在方法一中，我们使用了长度为 9 的数组表示每个数字是否出现过（1为出现过，0为没有出现）。我们同样也可以借助位运算，仅使用一个整数表示每个数字是否出现过。

具体的做法是：一个二进制数的第i位数（最低为是第0位）是1，就表示 i+1 已经出现过。例如：

二进制数 (011010100) 代表数字 3、5、7、8已经出现过。

也就是说我们用一个二进制数来表示一个哈希表。

在方法一中，每在一个空格出现一个数字num，或者是填写一个数字num，都要将这个空格对于行、列、3*3宫格的哈希表的num值由0变成1，也就是简单的[num-1]=1，填写完num发现数字不对后，又要将哈希表num的值由1变成0。也就是说，在用数组当作哈希表时，哈希表的更新就是将数组对应的值简单的0，1互换。

在此方法中，哈希表的更新就变成了二进制数对应某一位上的0，1互换。要使用一些位运算的技巧，

需要使用的位运算技巧

（1）、将二进制数的第i位由i变成0，或由0变成1.

1<<i 的第i+1位二进制数是1，其余的二进制数是0。x和1<<i按位异或后，x=x^(1<<i)后，x的第i+1位就实现了0，1的互换。

（2）、遍历一个二进制数上的所有0。

方法一中，空格所在的行、列、3*3宫格的哈希表[num-1]==0就代表这个空格可以填数字num，而在二进制的哈希表中，我们要找二进制数对应的0。二进制数的0不太好取，我们就把0，1互换，互换后的1就是先前的0，而二进制的1是好取的（随后会讲）。

一个二进制数按位取反得到的1就是先前的0，但是我们只需要前9位的1，所以取反后的数还要和（111111111）进行按位与操作，这样就能只留下前九位数。

（3）、取得二进制数最低位的1（包括后面的0）

x=~x&(111111111) 后，x中第i（从最低为第0位开始）位的1就代表数字 i+1可以填在空格里。

low_one=x&(-x)。因为-x在计算器用的是补码，所以-x和x的二进制数的最低为1和右边的0都相等，其余为都不想等，按位与刚好可以留下这一部分。留下这一部分后，low_one的位数就是可以填入空格的数字。

（4）、将二进制数的最低为1变成0。

在某个空格blanks中填入某个数后不一定对，这时候要填下一个数。我们只需要将最低位的1变成0，然后再取最低位的1，这样就取到了下一个数。

x&=(x-1);

代码

class Solution {
private:
    int rows[9];
    int cols[9];
    int boxes[3][3];
    vector<pair<int, int>> blanks;
    bool valid;
public:
    //将指定数位1变0，0变1
    void func(int i, int j, int digit) {
        rows[i] ^= (1 << digit);
        cols[j] ^= (1 << digit);
        boxes[i / 3][j / 3] ^= (1 << digit);
    }
    void backtrack(vector<vector<char>>& board, int index) {
        if (index == blanks.size()) {
            valid = true;
            return;
        }
        int x = blanks[index].first;
        int y = blanks[index].second;
        //创建掩码来遍历
        int mask = ~(rows[x] | cols[y] | boxes[x / 3][y / 3]);
        mask = mask & 0x1ff;            //和（111111111）按位取和，去除第九位之前的1
        while (mask && !valid) {
            //取最低位的1包括后面的0,然后转换成对应的数字
            int lowdigit = mask & (-mask);
            int digit = 0;
            while (lowdigit) {
                lowdigit >>= 1;
                digit++;
            }
            func(x, y, digit - 1);
            board[x][y] = '0' + digit;
            backtrack(board, index + 1);
            func(x, y, digit - 1);

            //去除掉最低位的1
            mask &= (mask - 1);
        }
    }
    void solveSudoku(vector<vector<char>>& board) {
        memset(rows, 0, sizeof(rows));
        memset(cols, 0, sizeof(cols));
        memset(boxes, 0, sizeof(boxes));
        valid = false;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    blanks.emplace_back(i, j);
                }
                else {
                    int digit = board[i][j] - '0' - 1;
                    func(i, j, digit);
                }
            }
        }

        backtrack(board, 0);
    }
};

位运算怎么就优化了呢？

对比一下方法一和方法二的代码。区别就是哈希表的更新和在遍历空格时，对于填充数字的遍历。

先说哈希表的更新，方法一的代码是

rows[i][digit-1]=columns[j][digit-1]=boxes[i/3][j/3][digit-1]=1;
或
rows[i][digit-1]=columns[j][digit-1]=boxes[i/3][j/3][digit-1]=0;

而方法二是对下面函数的一次调用。

void func(int i, int j, int digit) {
        rows[i] ^= (1 << digit);
        cols[j] ^= (1 << digit);
        boxes[i / 3][j / 3] ^= (1 << digit);
    }

光看这一部分来说，方法二反而要更复杂。

但是考虑到对空格填充数字的遍历时，那就不一样了。

方法一是对数字1-9都有一次判断，一共有九次。

for(int num=1;num<=9&&flag==false;num++){
    if(rows[x][num-1]==0&&columns[y][num-1]==0&&boxes[x/3][y/3][num-1]==0){
        //填充数字
    }
}

而方法二是在创建掩码后，每次只取对应二进制数位上有1的数。

//创建掩码来遍历
        int mask = ~(rows[x] | cols[y] | boxes[x / 3][y / 3]);
        mask = mask & 0x1ff;            //和（111111111）按位取和，去除第九位之前的1
        while (mask && !valid) {
            //填充数字
            mask &= (mask - 1);
        }

假设某个空格所在行、列、3*3宫格都只有一个数9可以填的时候，方法一需要循环9次，而方法二在创建掩码后，只需要循环1次。也就是说，方法二自动过滤掉了空格所在行、列、3*3宫格中已经出现的数。这大大缩短了代码运行时间。

方法三：枚举优化。

看了题解还知道，位运算的方法还能优化………………

想一下，我们在手作数独游戏的时候，都是先将能确定数字的位置先填上。

就比如在刚开始给出的矩阵中，有一个空格所在行出现过1、2、3，所在列出现过4、5、6，所在九宫格出现过7，8。那么毫无疑问，这个位置就是填9，不用等其他位置填完也能确认。

这样一来，我们可以不断地对整个数独进行遍历，将可以唯一确定的空白格全部填入对应的数。随后我们再使用与方法二相同的方法对剩余无法唯一确定的空白格进行递归 + 回溯。

官解代码

class Solution {
private:
    int line[9];
    int column[9];
    int block[3][3];
    bool valid;
    vector<pair<int, int>> spaces;

public:
    void flip(int i, int j, int digit) {
        line[i] ^= (1 << digit);
        column[j] ^= (1 << digit);
        block[i / 3][j / 3] ^= (1 << digit);
    }

    void dfs(vector<vector<char>>& board, int pos) {
        if (pos == spaces.size()) {
            valid = true;
            return;
        }

        auto [i, j] = spaces[pos];
        int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
        for (; mask && !valid; mask &= (mask - 1)) {
            int digitMask = mask & (-mask);
            int digit = __builtin_ctz(digitMask);
            flip(i, j, digit);
            board[i][j] = digit + '0' + 1;
            dfs(board, pos + 1);
            flip(i, j, digit);
        }
    }

    void solveSudoku(vector<vector<char>>& board) {
        memset(line, 0, sizeof(line));
        memset(column, 0, sizeof(column));
        memset(block, 0, sizeof(block));
        valid = false;

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    int digit = board[i][j] - '0' - 1;
                    flip(i, j, digit);
                }
            }
        }

        while (true) {
            int modified = false;
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    if (board[i][j] == '.') {
                        int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
                        if (!(mask & (mask - 1))) {
                            int digit = __builtin_ctz(mask);
                            flip(i, j, digit);
                            board[i][j] = digit + '0' + 1;
                            modified = true;
                        }
                    }
                }
            }
            if (!modified) {
                break;
            }
        }

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces.emplace_back(i, j);
                }
            }
        }

        dfs(board, 0);
    }
};

方法四：舞蹈链算法

我以为吕布已经天下无敌了，没想到有人比他还要勇猛…………

我翻看评论的时候，看到有个大佬发的一种算法，叫做舞蹈链算法，自称是解数独最快的算法，没有之一。这算法我也不会，直接把代码贴上来吧。

/*
最快的是舞蹈链算法
然后是贪心加回溯算法
最慢的是正常的回溯算法
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 9 * 9 * 9 * 4;

class node {
public:
    int u{}, d{}, l{}, r{}; //上下左右
    int row{}, col{};   //具体坐标
    int s{};          //col节点数量
    int h{};          //row头节点
    int ans{};        //选了那些row

    node() = default;
};

class DLX {
public:
    vector<vector<int>> a;
    const int n = 9 * 9 * 9, m = 9 * 9 * 4;
    int num{};
    vector<node> nodes;

    explicit DLX(vector<vector<int>> &B) {
        a = B;
        dance();
        B = a;
    }

    void dance() {
        init();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                for (int k = 1; k <= 9; k++) {
                    if (a[i][j] != k && a[i][j] != 0) {
                        continue;
                    }
                    int id = i * 9 * 9 + j * 9 + k;
                    Link(id, i * 9 + j + 1);
                    Link(id, i * 9 + k + 81);
                    Link(id, j * 9 + k + 162);
                    Link(id, (i / 3 * 3 + j / 3) * 9 + k + 243);
                }
            }
        }
        Dance(0);
    }

    void init() {
        num = m + 1;
        nodes.assign(N, node());
        for (int i = 0; i <= m; i++) {
            node &it = nodes[i];
            it.l = i - 1;
            it.r = i + 1;
            it.u = it.d = i;
        }
        nodes[0].l = m;
        nodes[m].r = 0;
    }

    void Link(int r, int c) {
        num++;
        node &row = nodes[r];
        node &col = nodes[c];
        node &nums = nodes[num];

        nums.row = r;
        nums.col = c;
        col.s++;

        // node[col.u] <-> nums <-> col
        nums.u = col.u;
        nodes[col.u].d = num;
        col.u = num;
        nums.d = c;

        if (row.h == 0) {
            row.h = nums.l = nums.r = num;
        } else {
            node &head = nodes[row.h];
            //node[head.l] <-> nums <-> head
            nums.l = head.l;
            nodes[head.l].r = num;
            head.l = num;
            nums.r = row.h;
        }
    }

    void Remove(int c) {
        node &col = nodes[c];
        // node[col.l] <-> node[col.r]
        nodes[col.l].r = col.r;
        nodes[col.r].l = col.l;

        //下右
        for (int i = col.d; i != c; i = nodes[i].d) {
            for (int j = nodes[i].r; j != i; j = nodes[j].r) {
                node &it = nodes[j];
                //node[it.u] <-> node[it.d]
                nodes[it.d].u = it.u;
                nodes[it.u].d = it.d;
                nodes[it.col].s--;
            }
        }
    }

    void Resume(int c) {
        // node[col.l] -> node[c] <- node[col.r]
        node &col = nodes[c];
        nodes[col.r].l = c;
        nodes[col.l].r = c;
        //上左
        for (int i = nodes[c].u; i != c; i = nodes[i].u) {
            for (int j = nodes[i].l; j != i; j = nodes[j].l) {
                node &it = nodes[j];
                //node[it.u] -> node[j] <- node[it.d]
                nodes[it.d].u = j;
                nodes[it.u].d = j;
                nodes[it.col].s++;
            }
        }
    }

    int Dance(int dep) { // NOLINT(*-no-recursion)
        if (nodes[0].r == 0) {
            for (int i = 0; i < dep; i++) {
                node &it = nodes[i];
                int x = (it.ans - 1) / 9 / 9;
                int y = (it.ans - 1) / 9 % 9;
                int val = (it.ans - 1) % 9 + 1;
                a[x][y] = val;
            }
            return 1;
        }
        int c = nodes[0].r;
        for (int i = nodes[0].r; i != 0; i = nodes[i].r) {
            if (nodes[i].s == 0 || nodes[c].s == 0) {
                return 0;
            }
            if (nodes[i].s < nodes[c].s) {
                c = i;
            }
        }
        Remove(c);
        for (int i = nodes[c].d; i != c; i = nodes[i].d) {
            node &it = nodes[i];
            nodes[dep].ans = it.row;
            for (int j = nodes[i].r; j != i; j = nodes[j].r) {
                Remove(nodes[j].col);
            }
            if (Dance(dep + 1) == 1) {
                return 1;
            }
            for (int j = nodes[i].l; j != i; j = nodes[j].l) {
                Resume(nodes[j].col);
            }
        }
        Resume(c);
        return 0;
    }
};

class Solution {
public:
    static void solveSudoku(vector<vector<char>> &b) {
        vector<vector<int>> a(9, vector<int>(9));
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int val = b[i][j] == '.' ? 0 : int(b[i][j] - '0');
                a[i][j] = val;
            }
        }
        DLX o(a);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                b[i][j] = char(a[i][j] + '0');
            }
        }
    }
};