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
``````

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;
}
};
``````