六感程序网站建设,河南建设厅八大员查询网站,百家号如何给网站做推广,公司接软件开发平台题目
37. 解数独
困难
相关标签
数组 哈希表 回溯 矩阵
编写一个程序#xff0c;通过填充空格来解决数独问题。
数独的解法需 遵循如下规则#xff1a;
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫…题目
37. 解数独
困难
相关标签
数组 哈希表 回溯 矩阵
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图
数独部分空格内已填入了数字空白格用 . 表示。 示例 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]]
解释输入的数独如上图所示唯一有效的解决方案如下所示 提示
board.length 9board[i].length 9board[i][j] 是一位数字或者 .题目数据 保证 输入数独仅有一个解
思路和解题方法 遍历行和列找到一个空白格子.。从 1 到 9 依次尝试填入数字判断当前数字是否合适放置在该格子位置。在 isValid 函数中首先检查当前数字在所在行和列是否重复出现如果重复则不合适。然后确定当前格子所在的 3x3 小方格起始位置再检查该小方格内是否存在重复的数字。如果当前数字合适则将其填入格子中并继续递归地调用回溯函数 backtracking以尝试解决剩下的空白格子。如果递归函数返回 true说明成功找到了一组合适的数独解法直接返回即可。如果递归函数返回 false说明当前尝试的数字不合适需要进行回溯操作撤销当前数字的填入并继续尝试下一个数字。如果遍历完所有的格子都没有返回 true说明无法得到有效解整个算法结束。 最终当算法完成后数独棋盘中的空白格子将被填满或者数独问题没有解。 c 代码
class Solution {
private:bool backtracking(vectorvectorchar board) {for (int i 0; i board.size(); i) { // 遍历行for (int j 0; j board[0].size(); j) { // 遍历列if (board[i][j] .) {for (char k 1; k 9; k) { // (i, j) 这个位置放k是否合适if (isValid(i, j, k, board)) {board[i][j] k; // 放置kif (backtracking(board)) return true; // 如果找到合适一组立刻返回board[i][j] .; // 回溯撤销k}}return false; // 9个数都试完了都不行那么就返回false}}}return true; // 遍历完没有返回false说明找到了合适棋盘位置了}bool isValid(int row, int col, char val, vectorvectorchar board) {for (int i 0; i 9; i) { // 判断行里是否重复if (board[row][i] val) {return false;}}for (int j 0; j 9; j) { // 判断列里是否重复if (board[j][col] val) {return false;}}int startRow (row / 3) * 3;int startCol (col / 3) * 3;for (int i startRow; i startRow 3; i) { // 判断9方格里是否重复for (int j startCol; j startCol 3; j) {if (board[i][j] val ) {return false;}}}return true;}public:void solveSudoku(vectorvectorchar board) {backtracking(board);}
};觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
