LeetCode 37. Sudoku Solver

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

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtrace(board, 0, 0);
    }
    bool backtrace(vector<vector<char>>& board, int i, int j){
        int m = 9, n = 9;
        if(j== n){
            return backtrace(board, i+1, 0);
        }
        if(i == m)
            return true;
        if(board[i][j] != '.'){
            return backtrace(board, i, j+1);
        }
        for(char ch = '1'; ch <= '9'; ch++){
            if(!isValid(board, i, j, ch))
                continue;
            board[i][j] = ch;
            if(backtrace(board, i, j+1))
                return true;
            board[i][j] = '.';
        }
        return false;
    }
    bool isValid(vector<vector<char>>& board, int r, int c, char ch){
        for(int i = 0; i < 9; i++){
            if(board[r][i] == ch)
                return false;
            if(board[i][c] == ch)
                return false;
            if(board[(r/3)*3 + i/3][(c/3)*3 + i%3] == ch)
                return false;
        }
        return true;
    }
};

详细解读参见：https://mp.weixin.qq.com/s/_jacgptmo4yNl516EQArrg