（难度Hard）Problem 37. Sudoku Solver（解数独）

### 链接

Sudoku Solver - LeetCode

Hard

### 题干

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

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
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...

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.

### 题解

#### 解法一 暴力搜索

void dfs(vector<vector<char>> board, int n) {
// n表示当前枚举的棋盘的位置，超过81说明整个棋盘已经填满
if (n == 81) return ;
// 计算n所代表的棋盘坐标
int x = n / 9;
int y = n % 9;
// 如果棋盘已有棋子，直接递归下一个位置
if (board[x][y] != '.') dfs(board, n+1);
// 枚举当前位置可以放置的棋子
for (int i = 0; i < 9; i++) {
char ch = '1' + i;
board[x][y] = ch;
// 递归
if (isValidSudoku(board)) {
dfs(board, n+1);
}
// 回溯，即清除这一步所放的棋子
board[x][y] = '.';
}
}

void solveSudoku(vector<vector<char>>& board) {
dfs(board, 0);
}

#### 解法二 搜索剪枝

`
// x，y表示放置的位置，k表示放置的元素
bool check(int x, int y, int k) {
su[x][y] = k;
// 计算得到九宫格左上角的点
int tx = x / 3 * 3;