解数独

class Solution {
public:
    bool back(vector<vector<char>>& board, int i, int j){
        if(i==board[0].size()){
            return true;
        }
        if(board[i][j]!='.'){
            if(j<board[0].size()-1){
                if(back(board, i, j+1)) return true;
            } 
            else{
                if(back(board, i+1, 0)) return true;
            }
            return false;
        }
        unordered_set<char> used={'1','2','3','4','5','6','7','8','9'};
        for(char k:used){
            if(is_valid(board, i, j, k)){
                board[i][j]=k;
                if(j<board[0].size()-1){
                    if(back(board, i, j+1)) return true;
                } 
                else{
                    if(back(board, i+1, 0)) return true;
                }
                board[i][j]='.';
            }
        }
        return false;
    }

    bool is_valid(vector<vector<char>>& board, int i, int j, char k){
        for(char c:board[i]){           // 行
            if(c==k) return false;
        }
        for(int z=0;z<board.size();z++){    // 列
            if(board[z][j]==k) return false;
        }
        for(int z=(i/3)*3;z<(i/3)*3+3;z++)
            for(int x=(j/3)*3;x<(j/3)*3+3;x++){
                if(board[z][x]==k) return false;
            }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        back(board, 0, 0);
    }
};


class Solution {
private:
bool backtracking(vector<vector<char>>& board) {
    for (int i = 0; i < board.size(); i++) {        // 遍历行
        for (int j = 0; j < board[0].size(); j++) { // 遍历列
            if (board[i][j] == '.') {
                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<vector<char>>& 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<vector<char>>& board) {
        backtracking(board);
    }
};