C++回溯解Leetcode 37難題數獨Sudoku

Backtracking solves the hard Sudoku puzzle, Leetcode 37, in C++.(內附以當代C++撰寫的快速解答)

The isValid function checks if a particular number can be placed in a specific position on the board without violating the Sudoku rules. It checks the corresponding row, column, and block arrays to ensure the number is unique. The solve function is the main recursive function that solves the Sudoku puzzle. 

It iterates through each cell in the board and checks if it is empty. If it is empty, it tries different numbers and checks their validity using the isValid function. If a valid number is found, it updates the board, calls itself recursively, and continues the process. 

If no valid number is found, it backtracks by undoing the previous choices and continues the search.
==============
用C++回溯解Leetcode 37的難題數獨。為何是難題？Leetcode這幾個數獨有的就要試上100K次以上，程式效能不好就TLE(Time Limit Exceeded)了。

isValid函數用於檢查特定位置是否可以放置某個數字，不違反數獨的規則。它檢查相應的行、列和區塊數組，以確保數字是唯一的。

solve函數是解數獨的主要遞迴函數。它遍歷棋盤中的每格，檢查它是否為空。如果為空，它嘗試不同的數字並使用isValid函數檢查它們的有效性。如果找到有效的數字，更新棋盤，遞迴函數呼叫自己並繼續過程。

如果找不到有效的數字，進行回溯，取消之前的選擇並繼續搜索。

[codes for Leecode]https://leetcode.com/problems/sudoku-solver/solutions/3622243/w-explaincc-solves-via-backtracking-bool-arrays-in-16-ms/
[C/C++/python解題Leetcode 36 Valid Sudoku有效數獨]https://www.youtube.com/watch?v=hkXrewUTqyc

[LeetCode程式]https://www.youtube.com/watch?v=7g-E3d_Oja4&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk&index=1

============== 

Using vector vector<pair<int, int>> uncertain as a stack to store the uncertain places is faster!!!!! It needs 11 ms and beats Beats 94.36%!

--------------

使用 vector<pair<int, int>> uncertain當成裝未確定數字的堆疊，跑得更快了，3 ms 且勝出99.27%!

class Solution {
    bool Row[9][9];
    bool Col[9][9];
    bool Block[9][9];
    vector<pair<int, int>> uncertain;
public:
     void print(vector<vector<char>>& board){
        for(vector<char>& row: board){
            for(char& c: row)
                cout<<c;
            cout<<endl;
        }
        cout<<"===========\n";
    }
    void set3Cond(int i, int j,  int x, bool val=1){
	Row[i][x] = val;
        Col[j][x] = val;
        int bidx = (i/3)*3 +j/3;
        Block[bidx][x] = val;
	}

    void setup(vector<vector<char>>& board) {
    	uncertain.reserve(81);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c=board[i][j];
                if ( c== '.') {
                    uncertain.push_back({i, j});
                }
                else {
                    int x=(c-'0')%9; 
                    set3Cond(i, j, x);
                }
            }
        }
    }

    bool solve(vector<vector<char>>& board) 
    {
        if (uncertain.empty()) 
            return 1; 
        auto [i, j]=uncertain.back();
        for (char c = '1'; c <= '9'; c++) {
            if (isValid(i, j, c)) {
                board[i][j] = c;
                uncertain.pop_back();
 
                int x=(c-'0')%9; 
                set3Cond(i, j, x);
				
                if (solve(board)) 
                    return 1;

                board[i][j] = '.'; // trace back
                uncertain.push_back({i, j});
                set3Cond(i, j, x, 0);
            }
        }
        return 0; 
    }

    bool isValid(int row, int col, char c) {
    	int x=(c-'0')%9;
        return !Row[row][x] && !Col[col][x] && !Block[(row/3)*3+col/3][x];
    }
    void solveSudoku(vector<vector<char>>& board) {
    //    print(board);
        setup(board);
        solve(board);
    //    print(board);
    }
};