一、题目描述

编写一个程序，通过填充空格来解决数独问题。

数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
数独部分空格内已填入了数字，空白格用 '.' 表示。

示例一：
输入：board = 
[["5", "3", ".", ".", "7", ".", ".", ".", "."],["6", ".", ".", "1", "9", "5", ".", ".", "."],[".", "9", "8", ".", ".", ".", ".", "6", "."],["8", ".", ".", ".", "6", ".", ".", ".", "3"],["4", ".", ".", "8", ".", "3", ".", ".", "1"],["7", ".", ".", ".", "2", ".", ".", ".", "6"],[".", "6", ".", ".", ".", ".", "2", "8", "."],[".", ".", ".", "4", "1", "9", ".", ".", "5"],[".", ".", ".", ".", "8", ".", ".", "7", "9"]
]
输出：
[["5", "3", "4", "6", "7", "8", "9", "1", "2"],["6", "7", "2", "1", "9", "5", "3", "4", "8"],["1", "9", "8", "3", "4", "2", "5", "6", "7"],["8", "5", "9", "7", "6", "1", "4", "2", "3"],["4", "2", "6", "8", "5", "3", "7", "9", "1"],["7", "1", "3", "9", "2", "4", "8", "5", "6"],["9", "6", "1", "5", "3", "7", "2", "8", "4"],["2", "8", "7", "4", "1", "9", "6", "3", "5"],["3", "4", "5", "2", "8", "6", "1", "7", "9"]
]

二、题解

通过回溯法求解，整体思路与N皇后问题相似，都是依次处理每个格子，同时通过一个 isValid 函数判断当前位置填充值的有效性。

同时因为题目中已经说明题目数据保证输入数独有且仅有一个解，因此我们需要让回溯函数返回值为布尔类型，这样只要遇到任意一种成功的情况，就立即依次返回。

class Solution {
public:void solveSudoku(vector<vector<char>> &board) {backtracking(board, 0, 0);}private:bool backtracking(vector<vector<char>> &board, int row, int col) {if (row == board.size()) {return true;}if (board.at(row).at(col) == '.') {for (int i = 1; i <= 9; i++) {board.at(row).at(col) = static_cast<char>(i + 48);if (isValid(board, row, col)) {if (col == board.size() - 1) {if (backtracking(board, row + 1, 0)) {return true;}} else {if (backtracking(board, row, col + 1)) {return true;}}}}board.at(row).at(col) = '.';} else {if (col == board.size() - 1) {if (backtracking(board, row + 1, 0)) {return true;}} else {if (backtracking(board, row, col + 1)) {return true;}}}return false;}bool isValid(vector<vector<char>> &board, int row, int col) {char c = board.at(row).at(col);/* 检查列重复 */for (int i = 0; i < board.size(); i++) {if (board.at(i).at(col) == c && i != row) {return false;}}/* 检查行重复 */for (int j = 0; j < board.size(); j++) {if (board.at(row).at(j) == c && j != col) {return false;}}/* 检查组内重复 */for (int i = (row / 3) * 3; i < ((row / 3) + 1) * 3; i++) {for (int j = (col / 3) * 3; j < ((col / 3) + 1) * 3; j++) {if (board.at(i).at(j) == c && i != row && j != col) {return false;}}}return true;}
};