Leetcode: 37. Sudoku Solver

Description

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

思路

• 非常常规的的一个dfs
• 借用36题中的bitset做映射，该位置0表未出现该数字，该位置1表出现
• 然后将9行，9列，9个小矩阵映射到27个bitset<9>上面

代码

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        int m = board.size();
        int n = board[0].size();
        vector<bitset<9>> flag(27, 0);
        int num = 0;
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n; ++j){
                if (board[i][j] == '.') continue;
                num = board[i][j] - '1';
                flag[i].set(num);
                flag[9 + j].set(num);
                flag[18 + (i / 3) * 3 + j / 3].set(num);
            }
        }

        solver(board, m, n, 0, 0, flag);
    }

    bool solver(vector<vector<char>> &board, int m, int n, int i, int j, vector<bitset<9>>& flag){
        
        while (i < m){
            if (j == n){
                j = 0;
                i++;
            }

            if (i < m && j < n && board[i][j] != '.'){
                j++;
                continue;
            }
            else break;
        }

        if (i == m) return true;

            for (int t = 0; t < 9; ++t){
                if (flag[i].test(t) || flag[9 + j].test(t) || flag[18 + (i / 3) * 3 + j / 3].test(t))
                    continue;

                board[i][j] = '1' + t;
                flag[i].set(t);
                flag[9 + j].set(t);
                flag[18 + (i / 3) * 3 + j / 3].set(t);
                if (solver(board, m, n, i, j + 1, flag)) return true;
                flag[i].set(t, 0);
                flag[9 + j].set(t, 0);
                flag[18 + (i / 3) * 3 + j / 3].set(t, 0);
                board[i][j] = '.';
            }
            
        return false;
    }
};

• 还没有人评论，欢迎说说您的想法！

相关课程

C++ 匠心之作 从0到1入门学编程

3872 9.8元

CSS3样式设计

4811 0元 限免

Scrapy爬虫框架

3870 9.8元