Sudoku Solver

LeetCode #37

Description:

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.

Example:

Note

Idea:

每个空格试一个值，然后再往下试，如果有conflict，就不成功，如果没有conflict，就是一个成功解。

Code:

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solveSudokuDFS(board, 0, 0);
    }

    bool solveSudokuDFS(vector<vector<char>>& board, int row, int column){
        int N=9;
        int i=row;
        int j;
        for(; i<N; ++i){
            if(i==row) j=column;
            else j=0;
            for(; j<N; ++j){
                if(board[i][j]=='.'){
                    for(int k=0; k<N; ++k){
                        board[i][j]=k+'1';
                        // this loc is good, the remaining are good as well
                        if(isValid(board, i, j) && solveSudokuDFS(board, i, j)){
                            return true;
                        }
                        board[i][j]='.';
                    }
                    return false;
                }
            }
        }
        return true;
    }

    bool isValid(vector<vector<char>>& board, int row, int column){
        int N=9;
        for(int i=0; i<N; ++i){
            if(i!=row && board[i][column]==board[row][column])
                return false;
        }
        for(int j=0; j<N; ++j){
            if(j!=column && board[row][j]==board[row][column])
                return false;
        }
        for(int i=3*(row/3); i<3*(row/3+1); ++i){
            for(int j=3*(column/3); j<3*(column/3+1); ++j){
                if((i!=row || j!=column) && board[i][j]==board[row][column])
                    return false;
            }
        }

        return true;
    }
};