# LeetCode37. Sudoku Solver（递归 / 回溯）

## LeetCode37. Sudoku Solver（递归 / 回溯）

• Hard
• Accepted：123,186
• Submissions：340,225

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

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

A sudoku puzzle...

...and its solution numbers marked in red.

Note:

• The given board contain only digits 1-9 and the character '.'.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9.

### 链接

https://leetcode.com/problems/sudoku-solver

### 代码

• Runtime: 16 ms, faster than 62.89% of C++ online submissions for Sudoku Solver.
• Memory Usage: 8.7 MB, less than 94.38% of C++ online submissions for Sudoku Solver.
class Solution {
private:
int n, m;
bool solve(vector<vector<char>>& board)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (board[i][j] == '.')
{
for (char c = '1'; c <= '9'; ++c)
{
if (check(board, i, j, c))
{
board[i][j] = c;
if (solve(board))
return true;
board[i][j] = '.'; // 回溯
}
}
return false;
}
}
}
return true;
}
bool check(vector<vector<char>>& board, int row, int col, char c)
{
for (int i = 0; i < 9; ++i)
{
int x = row / 3 * 3 + i / 3;
int y = col / 3 * 3 + i % 3;
if (board[row][i] == c || board[i][col] == c || board[x][y] == c)
return false;
}
return true;
}
public:
void solveSudoku(vector<vector<char>>& board) {
if (board.empty())
return ;
n = board.size(), m = board[0].size();
solve(board);
}
};

The end.
2019年4月15日 星期一