题目描述

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

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

1. 数字 1-9 在每一行只能出现一次
2. 数字 1-9 在每一列只能出现一次
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
   数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

来源：力扣（LeetCode）题目链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例1

输入：

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"]]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

题解1(按Board行列回溯：较直接)

class Solution {
public:
// 为什么回溯有返回值：因为只需要做一次解，需要及时返回；没有返回值的一般是需要穷举所有的解bool backtrace(vector<vector<char>>& board, int i, int j){if(9 == i){    // 回溯结束条件：以行为准return true;}else if(9 == j){return backtrace(board, i+1, 0);  // i行结束，换行+1}else if('.' != board[i][j]){return backtrace(board, i, j+1);  // 此处有数字了，换列}// 处理节点else{for(char c = '1'; c <= '9'; c++){ // 回溯枚举if(isvaild(board, i, j, c)){board[i][j] = c;if(backtrace(board, i, j+1))return true;  // 完成了一种解，剪枝board[i][j] = '.'; // 还没填完所有的空，回退}}}return false;}void solveSudoku(vector<vector<char>>& board) {backtrace(board, 0, 0);}bool isvaild(vector<vector<char>>& board, int i, int j, char c){for(int k=0; k<9; k++){// 同行if(c == board[i][k])return false;// 同列if(c == board[k][j])return false;// subboard：行/3 列/3 是找组别信息// 规律可循：一个subboard里，行列变化不同，行变一次，列变3次：// 所以一个除法，一个取余if(c == board[(i/3)*3+k/3][(j/3)*3+k%3])return false;}return true;}
};