leetcode 37 解数独

题目：37. 解数独

参考题解：解数独-代码随想录

记得以前杂志的后面，会附录些数独的题目。现在，我们用代码来求解。

思路：每个空格格，在遇到的时候，可能有不同的填充值。空格轮使用不同的值尝试。尝试失败，进行回溯，重新尝试。

不难哈，我在范围上多写了一个减一，导致大量的时间用于调试。

#include 
#include 
#include 

using namespace std;

class Solution {
public:
    void canAppear(const vector>& board, pair loc, vector& can_appr){
        // 给定数独，和某个位置。将位置目前可以填充的数字放入can_appr中

        set appred; // 保存所在行，列，正方形内出现过的数字
        
        // 正方形内出现过的数字
        pair upper_left_corner(loc.first/3*3,loc.second/3*3);
        for(int i=upper_left_corner.first; i nextLoc(const vector>& board,pair loc){
        // 当前位置的下一个位置
        if(loc.second nextPointLoc(const vector>& board,pair loc){
        // 当前位置的下一个'.'位置。或者，是超出范围的最后一行的下一行开头位置
        pair next_loc = nextLoc(board,loc);
        while(next_loc.first>& board,pair loc){
        // 题目数据 保证 输入数独仅有一个解
        // 从上向下，从左到右，填充数独

        // 填充完毕，返回
        if(loc.first == board.size())
            return true;
        

        if(board[loc.first][loc.second] != '.') // 已经存在数字，跳转到需要填充的位置。回溯过程中，仅开头可能会使用一次
            loc = nextPointLoc(board,loc); 
                
        vector can_appr;
        canAppear(board,loc,can_appr); // 统计目前当前位置可以出现的数字
        for(int k=0; k next_loc = nextPointLoc(board,loc); // 计算下一个需要填充的位置

            // for(auto vec : board){
            //     for(auto ch : vec)
            //         cout<>& board) {
        backTracking(board,{0,0});
    }
};


int main(void){
    vector> 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'}};
    Solution s;
    s.solveSudoku(board);
    for(auto vec : board){
        for(auto ch : vec)
            cout< 
参考题解的大体思路和上面相同。但是，参考题解比我的代码质量相对要好。
 
下面代码来自参考题解。
 
class Solution {
private:
bool backtracking(vector>& board) {
    for (int i = 0; i < board.size(); i++) {        // 遍历行
        for (int j = 0; j < board[0].size(); j++) { // 遍历列
            if (board[i][j] != '.') continue;
            for (char k = '1'; k <= '9'; k++) {     // (i, j) 这个位置放k是否合适
                if (isValid(i, j, k, board)) {
                    board[i][j] = k;                // 放置k
                    if (backtracking(board)) return true; // 如果找到合适一组立刻返回
                    board[i][j] = '.';              // 回溯，撤销k
                }
            }
            return false;                           // 9个数都试完了，都不行，那么就返回false
        }
    }
    return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}
bool isValid(int row, int col, char val, vector>& board) {
    for (int i = 0; i < 9; i++) { // 判断行里是否重复
        if (board[row][i] == val) {
            return false;
        }
    }
    for (int j = 0; j < 9; j++) { // 判断列里是否重复
        if (board[j][col] == val) {
            return false;
        }
    }
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == val ) {
                return false;
            }
        }
    }
    return true;
}
public:
    void solveSudoku(vector>& board) {
        backtracking(board);
    }
};