LeetCode37-解数独

桃扇骨 2023-07-10 11:27 12阅读 0赞

### 1 题目描述 ###

编写一个程序，通过已填充的空格来解决数独问题。一个数独的解法需遵循如下规则：

*  数字 1-9 在每一行只能出现一次。
 *  数字 1-9 在每一列只能出现一次。
 *  数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 *  空白格用 ‘.’ 表示。

**Note:**

*  给定的数独序列只包含数字 `1-9` 和字符 `'.'` 。
 *  你可以假设给定的数独只有唯一解。
 *  给定数独永远是 `9x9` 形式的。

### 2 题解 ###

解数独基本没有特别好的方法，让笨笨的计算机去解数独它只会回溯。大致的思路：递归求解数独就按照从左往右从上往下的顺序逐个试过去，如果不符合数独的规则则回溯到上一个状态。

`小trick`

在进行回溯之前，先遍历一遍数独矩阵，将空位置的坐标记下来，在回溯的时候逐个访问空坐标。话不多说，直接看代码吧：

`C++代码`

class Solution {
        
    public:
        bool check(vector<vector<char>> & board, int row, int col) {
        
            // check row
            for (int i = 0; i < 9; i++) 
                if (i != col && board[row][i] == board[row][col]) return false;
            // check col
            for (int i = 0; i < 9; i++) 
                if (i != row && board[i][col] == board[row][col]) return false;
            // check block
            for (int i = (col / 3) * 3; i < (col / 3) * 3 + 3; i++) {
        
                for (int j = (row / 3) * 3; j < (row / 3) * 3 + 3; j++) {
        
                    if (i != col && j != row && board[j][i] == board[row][col]) return false;
                }
            }
            return true;
        }
    
        bool helper(vector<vector<char>>& board, vector<int> &blank_list, int index) {
        
            if (index == blank_list.size()) {
        
                return true;
            }
    
            int row = blank_list[index] / 9;
            int col = blank_list[index] % 9;
    		bool ret = false;
            for (int i = 1; i <= 9; i++) {
        
                board[row][col] = '0' + i;
                if (ret == false && check(board, row, col)) 
                    ret = helper(board, blank_list, index + 1);
                if (ret == true) 
                    return true; 
    			board[row][col] = '.';
            }
    		return false;
        }
    
        void solveSudoku(vector<vector<char>>& board) {
        
            vector<int> blank_list;
            for (int i = 0; i < 9; i++) {
        
                for (int j = 0; j < 9; j++) {
        
                    if (board[i][j] == '.') blank_list.push_back(i * 9 + j);
                }
            }
            helper(board, blank_list, 0);
        }
    };