https://leetcode.cn/problems/sudoku-solver/description/

<aside> 💡

这题与N皇后不同，是真的二维。

• 可以将所有行头尾相连，仍然当作一维序列来遍历。
• 使用了三个used数组分别保存行、列、块中1-9各个数字的使用情况 </aside>

// 第一维代表编号，第二维记录索引对应的数字是否使用过
// 默认初始化为false
bool usedRow[9][9];
bool usedCol[9][9];
bool usedBlock[9][9];

vector<vector<char>> ans;

void backtracking(int row, int col, vector<vector<char>>& board) {
		// 每行从左往右填空，填完一行跳转到下一行开头继续填
		if (col == 9) {
				col = 0;
				++row;
				// 填完所有行时说明完成所有填空，记录结果并返回
				if (row == 9) {
						ans = board;
						return;
				}
		}
		// 如果此处是已经填充好的，直接进入下一层递归
		if (board[row][col] != '.')
				backtracking(row, col + 1, board);
		else {
				// 遍历1-9，如果能填就填入并进入下一格
				for (int n = 1; n <= 9; ++n) {
						if (usedRow[row][n - 1] || usedCol[col][n - 1] || usedBlock[(row / 3) * 3 + (col / 3)][n - 1])
								continue;
			
						// 操作
						board[row][col] = '0' + n;
						usedRow[row][n - 1] = true;
						usedCol[col][n - 1] = true;
						usedBlock[(row / 3) * 3 + (col / 3)][n - 1] = true;
						//递归
						backtracking(row, col + 1, board);
						// 回溯
						usedRow[row][n - 1] = false;
						usedCol[col][n - 1] = false;
						usedBlock[(row / 3) * 3 + (col / 3)][n - 1] = false;
						board[row][col] = '.';
				}
		}
}

void solveSudoku(vector<vector<char>>& board) {
	// 初始化三个used数组
	for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) {
					char c = board[i][j];
					if (c != '.') {
							usedRow[i][c - '0' - 1] = true;
							usedCol[j][c - '0' - 1] = true;
							usedBlock[(i / 3) * 3 + (j / 3)][c - '0' - 1] = true;
					}
			}
	}
	backtracking(0, 0, board);
	board = ans;
}