回溯
解题思路
递归函数的返回值为什么需要是 boolean 类型呢？
- 因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回；
- 相当于找从根节点到叶子节点一条唯一路径，所以需要使用 boolean 返回值；
不用终止条件会不会死循环？递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件；
那么有没有永远填不满的情况呢？
- 一个 for 循环遍历棋盘的行，一个 for 循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放 9 个数字的可能性；
- 因为一行一列确定下来了，如果尝试了 9 个数都不行，说明这个棋盘找不到解决数独问题的解，那么会直接返回， 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去；
图解
代码实现
var solveSudoku = function (board) {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[i][j] !== '.') continue;
for (let num = 1; num <= 9; num++) { // 开始放数字 1~9
num = num.toString();
// 判断数独是不是合理
if (isValid(board, i, j, num)) {
board[i][j] = num;
if (solveSudoku(board)) return true;
board[i][j] = '.';
}
}
// 9个数都试完了都不行，那么就返回 false,说明这个棋盘找不到解决数独问题的解
return false;
}
}
return true;
};
// 校验是否是数独
const isValid = (board, row, col, num) => {
// 当前行、列 是否有重复
for (let i = 0; i < 9; i++) {
if (board[row][i] === num || board[i][col] === num) return false;
}
// x、y 为宫的左上角的坐标
const x = Math.floor(row / 3) * 3; // 判断在 上中下 哪一宫
const y = Math.floor(col / 3) * 3; // 判断在 左中右 哪一宫
// 当前宫里面 是否有重复
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[x + i][y + j] == num) return false;
}
}
return true; // 没有重复
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 51. N 皇后
上一篇
评论
