解数独

题目表述

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 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)
}