一天一大 lee(解数独)难度:困难-Day20200915
程序员文章站
2022-05-08 14:34:41
...
题目:
编写一个程序,通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。
一个数独。
答案被标成红色。
Note:
- 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
- 你可以假设给定的数独只有唯一解。
- 给定数独永远是 9x9 形式的。
抛砖引玉
思路
- 对应任意一个字符 '.'填充的单元格,记录他所在行、列、3X3 子块传下过的数组
- 对其填充可能是数组,并且递归继续向后填充:
- 如果填充完所有符号’.'则直接结束
- 如果未填充完则说明填充错误,需要重置填充状态重新填充
填充数记录:
- 行:9X9 的矩阵 line[i][k],
- i 为行索引;
- k 是行内出现过的数字(恢复到 board 内元素需要+1);
- 值是否出现,出现过 true
- 列:9X9 的矩阵 column[i][k],
- i 为列索引;
- k 是行内出现过的数字(恢复到 board 内元素需要+1);
- 值是否出现,出现过 true
- 子块:3X3 的矩阵,内存放长度为 9 的数组 block[i][j][k],
- i 为行索引;
- j 为列索引;
- k 是行内出现过的数字(恢复到 board 内元素需要+1);
- 值是否出现,出现过 true
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solveSudoku = function(board) {
let line = Array.from({ length: 9 }, () => Array(9)),
column = Array.from({ length: 9 }, () => Array(9)),
// 3x3 宫
block = Array.from({ length: 3 }, () => Array(3)),
// 任意一种组合满足要求,终止递归
isEnd = false,
// 待填充的坐标
spaces = []
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
block[i][j] = Array(9)
}
}
// 初始化行、列、子块数据
for (let i = 0; i < 9; ++i) {
for (let j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
spaces.push([i, j])
} else {
// 注意:数字是1-9,校验的行、列、子块数据索引是0-8,所以标记时值需要-1
let k = board[i][j] - 1,
// 子块坐标
x = parseInt(i / 3, 10),
y = parseInt(j / 3, 10)
line[i][k] = true
column[j][k] = true
block[x][y][k] = true
}
}
}
dfs(board, 0)
function dfs(board, index) {
if (index == spaces.length) {
isEnd = true
return
}
// 递归这个填充board中的字符 '.'
let [i, j] = spaces[index]
for (let k = 0; k < 9 && !isEnd; ++k) {
let x = parseInt(i / 3, 10),
y = parseInt(j / 3, 10)
// 行内、列内、子块内无当前枚举数字则填充
if (!line[i][k] && !column[j][k] && !block[x][y][k]) {
line[i][k] = true
column[j][k] = true
block[x][y][k] = true
board[i][j] = k + 1
// 递归填充下一个,如果递归为遇到终止逻辑则说明本地填充错误
dfs(board, index + 1)
// 将填充状态恢复到未填充
line[i][k] = false
column[j][k] = false
block[x][y][k] = false
}
}
}
}
博客: 小书童博客
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目
欢迎关注留言
推荐阅读
-
一天一大 lee(解数独)难度:困难-Day20200915
-
【一天一大 lee】单词拆分 II (难度:困难) - Day20201101
-
一天一大 lee(冗余连接 II)难度:困难-Day20200917
-
【一天一大 lee】最大间距 (难度:困难) - Day20201126
-
一天一大 lee(N 皇后)难度:困难-Day20200903
-
【一天一大 lee】N皇后 II (难度:困难) - Day20201017
-
【一天一大 lee】插入区间 (难度:困难) - Day20201104
-
一天一大 lee(24点游戏)难度:困难-Day20200822
-
一天一大 lee(回文对)难度:困难-Day20200806
-
一天一大 lee(最短回文串)难度:困难-Day20200829