解数独
题目表述
编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
数字 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 == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解
解法一:深度优先搜索
通过长度为 9 的数组记录对应行、列、和 3x3 单元格是否有对应元素被访问;将待访问元素加入列表,然后深度优先递归遍历。
代码实现
from typing import List
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def dfs(pos: int):
nonlocal valid
if pos == len(spaces):
valid = True
return
i, j = spaces[pos]
for digit in range(9):
if (
line[i][digit]
== column[j][digit]
== block[i // 3][j // 3][digit]
== False
):
line[i][digit] = column[j][digit] = block[i // 3][j // 3][
digit
] = True
board[i][j] = str(digit + 1)
dfs(pos + 1)
line[i][digit] = column[j][digit] = block[i // 3][j // 3][
digit
] = False
if valid:
return
line = [[False] * 9 for _ in range(9)]
column = [[False] * 9 for _ in range(9)]
block = [[[False] * 9 for _a in range(3)] for _b in range(3)]
valid = False
spaces = list()
for i in range(9):
for j in range(9):
if board[i][j] == ".":
spaces.append((i, j))
else:
digit = int(board[i][j]) - 1
line[i][digit] = column[j][digit] = block[i // 3][j // 3][
digit
] = True
dfs(0)
package leetcode
// solveSudoku 将1~9数字是否出现转为数组是否被访问,深度优先遍历
func solveSudoku(board [][]byte) {
var row, column [9][9]bool
var block [3][3][9]bool
var spaces [][2]int
// 初始化:取出空位置,并将非空位置进行标记
for i, vrow := range board {
for j, v := range vrow {
if v == '.' {
spaces = append(spaces, [2]int{i, j})
} else {
digit := v - '1'
row[i][digit], column[j][digit], block[i/3][j/3][digit] = true, true, true
}
}
}
var dfs func(pos int) bool
dfs = func(pos int) bool {
if pos == len(spaces) {
return true
}
i, j := spaces[pos][0], spaces[pos][1]
for digit := byte(0); digit < 9; digit++ {
if !row[i][digit] && !column[j][digit] && !block[i/3][j/3][digit] {
// 标记为已访问
row[i][digit], column[j][digit], block[i/3][j/3][digit] = true, true, true
board[i][j] = digit + '1'
// 递归访问下一个点
if dfs(pos + 1) {
return true
}
// 未到达最终结果,则取消标记
row[i][digit], column[j][digit], block[i/3][j/3][digit] = false, false, false
}
}
return false
}
dfs(0)
}