来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sudoku-solver
题目描述
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 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"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解
解题思路
数独问题是个np问题，只能采用回溯算法来求解。
将行列和块分别使用一个九位的二进制数作为标志，分别表示他们区域内1-9数字的使用情况，将需要填充的格子坐标写入一个栈中，然后利用深度优先的算法尝试为格子填入合法的数字。
代码展示
class Solution { public: vector<int> viRow, viCol; vector<vector<int>> vviBlock; stack<pair<int, int>> vpairiiNeed; void dfs(vector<vector<char>>& board, bool &Flag) { if(vpairiiNeed.empty()) Flag = true; if(Flag) return; auto Temp = vpairiiNeed.top(); vpairiiNeed.pop(); for(int i = 0; i < 9; i++) { if(viRow[Temp.first] & (1 << i)) continue; if(viCol[Temp.second] & (1 << i)) continue; if(vviBlock[Temp.first / 3][Temp.second / 3] & (1 << i)) continue; board[Temp.first][Temp.second] = i + '1'; viRow[Temp.first] += 1 << (board[Temp.first][Temp.second] - '1'); viCol[Temp.second] += 1 << (board[Temp.first][Temp.second] - '1'); vviBlock[Temp.first / 3][Temp.second / 3] += 1 << (board[Temp.first][Temp.second] - '1'); dfs(board, Flag); if(Flag) break; viRow[Temp.first] -= 1 << (board[Temp.first][Temp.second] - '1'); viCol[Temp.second] -= 1 << (board[Temp.first][Temp.second] - '1'); vviBlock[Temp.first / 3][Temp.second / 3] -= 1 << (board[Temp.first][Temp.second] - '1'); } if(!Flag) { vpairiiNeed.push(Temp); } } void solveSudoku(vector<vector<char>>& board) { viRow.resize(9, 0); viCol.resize(9, 0); vviBlock.resize(3, vector<int>(3, 0)); bool Flag = false; for(int i = 0; i < 9; i++) for(int j = 0; j < 9; j++) { if(board[i][j] == '.') vpairiiNeed.push({i, j}); else { viRow[i] += 1 << (board[i][j] - '1'); viCol[j] += 1 << (board[i][j] - '1'); vviBlock[i / 3][j / 3] += 1 << (board[i][j] - '1'); } } dfs(board, Flag); } };
运行结果
