LeedCode 37. 解数独

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

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

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

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

 

示例：

输入：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] 是一位数字或者 '.'
    题目数据 保证 输入数独仅有一个解

• 二进制优化， 一共有9个数字，那么用9位二进制代表每个数，若该位置为1代表这个数可以在该位置填入。
• 如何进行剪枝呢，我们可以从搜索分支少的点开始进行搜索，开始的分支少，那么搜索的次数便会减少。每个位置可以搜索的点便是grid ， row, col三个数组的并集，二进制上的1代表可以填，那么3个数组都满足就是最后能填入的数。
• lowbit获取可以填入1的位置，遍历所有的1即是能填入的数。

class Solution {
public:
    int cnt = 81;
    void solveSudoku(vector>& board) { 
        vector> grid(9, vector(10));
        vector> row(9, vector(10));
        vector> col(9, vector(10));
        init(board, grid, row, col);
        dfs(board, grid, row, col, 0, 0);
    }
    void init(vector>& board, vector>& grid, vector>& row, vector>& col) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int idx = i / 3 * 3 + j / 3;
                    int t = board[i][j] - '0';
                    grid[idx][t] = 1;
                    row[i][t] = 1;
                    col[j][t] = 1;
                    cnt--;
                }
            }
        }
    }
    bool dfs(vector>& board, vector>& grid, vector>& row, vector>& col, int i, int j) {
        if (cnt == 0) return true;
        //每次从下一个位置开始搜索
        while (board[i][j] != '.') {
            if (++j >= 9) {
                i++;
                j = 0;
            }
            if (i >= 9) return true;
        }
        if (board[i][j] == '.') {
            for (int k = 1; k <= 9; k++) {
                int idx = i / 3 * 3 + j / 3;
                if (!grid[idx][k] && !row[i][k] && !col[j][k]) {
                    board[i][j] = char(k + '0');
                    grid[idx][k] = 1;
                    row[i][k] = 1;
                    col[j][k] = 1;
                    cnt--;
                    //printf("%d-%d-%cn", i + 1, j + 1, board[i][j]);
                    if (dfs(board, grid, row, col, i, j)) return true;
                    cnt++;
                    board[i][j] = '.';
                    grid[idx][k] = 0;
                    row[i][k] = 0;
                    col[j][k] = 0;
                } 
            }     
        }
        return false;
    }
};

• 二进制优化

class Solution {
public:
    unordered_map mp;
    void solveSudoku(vector>& board) { 
        vector grid(9);
        vector row(9);
        vector col(9);
        vector help((1 << 9)); 
        int cnt = 81;
        vector> g;
        for (int i = 0; i < 9; i++) {
            mp[1 << i] = i;
            grid[i] = (1 << 9) - 1;
            row[i] = (1 << 9) - 1;
            col[i] = (1 << 9) - 1; 
        }
        //统计每个二进制有多少个1
        for (int i = 0; i < (1 << 9); i++) {
            int cnt = 0;
            for (int j = i; j; j -= lowbit(j)) cnt++;
            help[i] = cnt;
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int t = board[i][j] - '1';
                    int idx = i / 3 * 3 + j / 3;
                    grid[idx] -= 1 << t;
                    row[i] -= 1 << t;
                    col[j] -= 1 << t;
                    cnt--;
                }
            }
        }
        dfs(board, grid, row, col, help, cnt);
    }
    int lowbit(int x) {
        return x & (-x);
    }
    int get(int i, int j, vector& grid, vector& row, vector& col) {
        return grid[i / 3 * 3 + j / 3] & row[i] & col[j];
    }
    bool dfs(vector>& board, vector& grid, vector& row, vector& col, vector& help, int ct) {
        //找出搜索范围最小的位置进行填数 即1个数最少的点
        if (ct == 0) return true;
        int x = 0, y = 0, minv = 20;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    int cnt = help[get(i, j, grid, row, col)];
                    if (cnt < minv) {
                        x = i, y =j;
                        minv = cnt;
                    }
                }
            }
        }
        //从(x,y)这个位置开始进行搜索
        for (int j = get(x, y, grid, row, col); j; j -= lowbit(j)) {
            grid[x / 3 * 3 + y / 3] -= lowbit(j);
            row[x] -= lowbit(j);
            col[y] -= lowbit(j);
            board[x][y] = char(mp[lowbit(j)] + '1');
            if (dfs(board, grid, row, col, help, ct - 1)) return true;
            board[x][y] = '.';
            grid[x / 3 * 3 + y / 3] += lowbit(j);
            row[x] += lowbit(j);
            col[y] += lowbit(j);            
        }
        return false;
    }
};