题解 | #数独#

一.题目描述
NC47数独
题目链接:
https://www.nowcoder.com/practice/5e6c424b82224b85b64f28fd85761280?tpId=196&&tqId=37077&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
请编写一个程序，给数独中的剩余的空格填写上数字，空格用字符'.'表示，假设给定的数独只有唯一的解法。
二.算法(搜索)

思考：利用暴力搜索对每一种情况进行合法性判断，可以设置三个搜索变量dfs(board,x,y):
(1)(x,y)表示搜索坐标，那么每一个小数组中任意一个坐标可以表示为：
1.横坐标-(x/3)3+i/3
2.纵坐标-(y/3)3+i%3
(2)board表示要被搜索的数独二维数组
思路：经典的搜索问题，和八皇后问题类似，关键实现一个合法性判断函数,isValid(x,y,c)即在(x,y)位置放入c字符是否可行 ,即行不能重复 ,列不能重复,九宫格不能重复dfs(x,y,c) 当遇到存在字符时跳过。空格时，填入isValid可行的字符，并跳转到下一个dfs(board,x，y+1),当index==81即所有字符填充完毕时，是最终结束搜索，迅速返回，可采取标记变量方式。
下面是代码:

#include <vector>

using namespace std;

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        //从(0,0)位置开始搜索
        dfs(board, 0, 0);
    }
    bool dfs(vector<vector<char> > &board, int x, int y) {
        if (x==9) return true;
        if (y==9) return dfs(board,x+1,0);//表示该列已经检验完了 对下一行进行检验
        //如果被数字占位置了 直接进入下一列
        if (board[x][y] != '.')  return dfs(board, x, y+1);
        //遍历1-9进行暴力判断 填入是否合法
        for (char c='1';c<='9';c++) {
            //利用isValid对填入字符进行判断是否合法
            if (!isValid(board, x, y, c)) continue;
            //回溯操作
            board[x][y] = c;
            if (dfs(board,x,y+1)) return true;
            board[x][y] = '.';
        }
        return false;
    }

    bool isValid(vector<vector<char> > &board, int x, int y, char ch) {
        for (int i = 0; i < 9; ++i) {
            //分别从三个方面进行检验
            //所在列是不是有相同数字
            if (board[x][i] == ch) return false;
            //所在行是不是有相同数字
            if (board[i][y] == ch) return false;
            //所在的小矩形是不是有相同数字
            if (board[(x/3)*3 + i/3][(y/3)*3 + i%3] == ch) return false;
        }
        return true;
    }
};

时间复杂度:o(n*n)其中n为数独的横纵大小
空间复杂度:o(1) 不需要开辟额外空间
优缺点:思考过程和实现简单，但是时间复杂度比较高

三.算法(位运算优化)
在算法二中，我们使用了暴力检验每一个状态是不是合法。我们同样也可以借助位运算，仅使用一个整数表示每个数字是否出现过。
具体地，数b的二进制表示的第i位(从低到高，最低位为第0位)为 11，当且仅当数字i+1已经出现过。例如当b的二进制表示为 (011000100)2时候，就表示3，7，8已经出现过。

下面直接来看代码:

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];
        //0x1ff 表示全为1 表全部填入了数字
        int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
        for (; mask && !valid; mask &= (mask - 1)) {
            int digitMask = mask & (-mask);
            //找到最低位的非0位置
            int digit = __builtin_ctz(digitMask);
            //内置函数__builtin_ctz：返回前导的0的个数。
            //回溯
            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] == '.') {
                    //要是没有填入直接放入spaces 进行填入
                    spaces.emplace_back(i, j);
                    //emplace_back省去了移动构造函数 效率高
                } else {
                    int digit = board[i][j] - '0' - 1;
                    flip(i,j,digit);
                }
            }
        }
        dfs(board, 0);
    }
};

时间复杂度：o(1)
空间复杂度：o(n * n)需要开辟额外的空间
优缺点：位运算优化难实现，但是时间效率很高