针织东莞网站建设技术支持,崇明手机网站建设,网页制作素材网站推荐,免费软件网站建设题目链接#xff1a;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] 是一位数字或者 .题目数据 保证 输入数独仅有一个解
文章讲解代码随想录
视频讲解回溯算法二维递归解数独不过如此| LeetCode37. 解数独_哔哩哔哩_bilibili
题解1回溯法
思路使用回溯法求解棋盘类问题。
回溯分析
递归函数的参数和返回值返回值是一个布尔值表示是否填充完毕。参数为 num表示当前已填充几个数字。递归函数的终止条件num 等于81即填充完整个数独。单层递归的逻辑若当前格还未填充则从1到9尝试填充然后递归的填充下一格已填充则直接递归的填充下一格。剪枝当与其他格数字冲突时跳过本次填充。
/*** param {character[][]} board* return {void} Do not return anything, modify board in-place instead.*/
var solveSudoku function(board) {const rowState new Array(9).fill().map(() new Array(9).fill(false)); // 行状态const colState new Array(9).fill().map(() new Array(9).fill(false)); // 列状态const squierState new Array(3).fill().map(() new Array(3).fill().map(() new Array(9).fill(false))); // 单元状态// 初始化状态表for (let i 0; i 9; i) {for (let j 0; j 9; j) {if (board[i][j] .) {continue;}rowState[i][board[i][j]] true;colState[j][board[i][j]] true;squierState[parseInt(i / 3)][parseInt(j / 3)][board[i][j]] true;}}const backtracking function (num) {if (num 81) {return true; // 填充完毕返回 true}const col num % 9; // 计算列数const row (num - col) / 9; // 计算行数if (board[row][col] ! .) {return backtracking(num 1); // 已经有数字了向下遍历}// 从1到9尝试填充for (let j 1; j 9; j) {// 和规则冲突尝试填充下一个数if (rowState[row][j] || colState[col][j] || squierState[parseInt(row / 3)][parseInt(col / 3)][j]) {continue;}board[row][col] j; // 填充rowState[row][j] true; // 更新行状态colState[col][j] true; // 更新列状态squierState[parseInt(row / 3)][parseInt(col / 3)][j] true; // 更新单元状态// 向下遍历if (backtracking(num 1)) {return true; // 已经填充完毕返还 true}// 回溯board[row][col] .;rowState[row][j] false;colState[col][j] false;squierState[parseInt(row / 3)][parseInt(col / 3)][j] false;}return false;}backtracking(0);
};
分析设 m 为 . 的数量则时间复杂度为 O(9 ^ m)空间复杂度为 O(n²)。
收获
练习使用回溯法求解棋盘类问题和 n 皇后问题不同的是本题需要填充一个二维数组。
