Sudoku Solver

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

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

深搜加回溯剪枝。

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        dfs(board, 0);
    }
    bool dfs(vector<vector<char >> &board, int idx){
        int r,c;
        //找到空的格子
        while(true){
            if(idx >= 9 * 9){
                return true;
            }
            r = idx / 9;
            c = idx % 9;
            if(board[r][c] == '.'){
                break;
            }         
            idx++;
        }
        for(int i = 1; i < 10;i++){
            board[r][c] = '0' + i;
            if(isValid(board, r, c)){
                bool state = dfs(board, idx + 1);
                if(state == true){
                    return true;
                }
            }
        }
        board[r][c] = '.';
        return false;
    }
    //插入数字到x行y列，检查是否合法
    bool isValid(vector<vector<char >> &board, int x, int y){
        bool row[10] = {false};
        bool column[10] = {false};
        bool cell[10] = {false};
        //check row
        for(int i = 0; i < 9; i++){
            char c = board[x][i];
            if(c == '.'){
                continue;
            }
            else{
                if(row[c - '0'] == true){
                    return false;
                }
                else{
                    row[c - '0'] = true;
                }
            }
        }
        for(int i = 0; i < 9; i++){
            char c = board[i][y];
            if(c == '.'){
                continue;
            }
            else{
                if(column[c - '0'] == true){
                    return false;
                }
                else{
                    column[c - '0'] = true;
                }
            }
        }
        int rowStart = x / 3 * 3;
        int columnStart = y / 3 * 3;
        for(int i = 0; i < 9; i++){
            char c = board[rowStart + i / 3][columnStart + i % 3];
            if(c == '.'){
                continue;
            }
            else{
                if(cell[c - '0'] == true){
                    return false;
                }
                else{
                    cell[c - '0'] = true;
                }
            }
        }
        return true;
    }
};