# [leetcode] Sudoku Solver

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.