# [Leetcode] 37. Sudoku Solver 解题报告

2017-01-03 09:38:00      个评论    来源：魔豆（Magicbean）的博客

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, 0);
}
private:
bool DFS(vector<vector<char>>& board, int row, int col)
{
if(row == 9)
return true;
if(col == 9)                                // try next row
return DFS(board, row + 1, 0);
if(board[row][col] != '.')                  // try next col
return DFS(board, row, col + 1);
for(int i = 1; i <= 9; i++)
{
int a, b;
for(a = 0; a < 9; a++)
if(board[row][a] == '0' + i)
break;
if(a != 9)                              // i already exists in this row
continue;
for(a = 0; a < 9; a++)
if(board[a][col] == '0' + i)
break;
if(a != 9)                              // i already exists in this col
continue;
for(a = row/3*3; a < row/3*3+3; a++)
{
for(b = col/3*3; b < col/3*3+3; b++)
if(board[a][b] == '0'+i)
break;
if(b != col/3*3+3)
break;
}
if(!(a == row/3*3+3 && b == col/3*3+3)) // i already exists in this grid
continue;
board[row][col] = '0' + i;
if(DFS(board, row, col + 1))            // try next col
return true;
board[row][col] = '.';                  // backtracking
}
return false;
}
};```