image.png
0. 链接
1. 题目
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.
image.png
A sudoku puzzle...
image.png
...and its solution numbers marked in red.
Note:
- The given board contain only digits 1-9 and the character '.'.
- You may assume that the given Sudoku puzzle will have a single unique solution.
- The given board size is always 9x9.
2. 思路： 深度优先搜索
- 先统计每行，每列，每个九宫格的数字集合
- 按行列的顺序，对每个格子逐个尝试未出现过的数字，对每个假设的数字，继续在此基础上尝试后续所有格子；
- 当一个假设不满足条件的，继续尝试下一个数字，最终找到唯一符合条件的数字。
3. 代码
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
row_check = [set() for i in range(9)]
col_check = [set() for i in range(9)]
grid_check = [[set() for i in range(3)] for j in range(3)]
def dfs(i, j, board, row_check, col_check, grid_check):
if i == 9:
return True
if j == 9:
return dfs(i + 1, 0, board, row_check, col_check, grid_check)
if board[i][j] != '.':
return dfs(i, j + 1, board, row_check, col_check, grid_check)
for value in range(1, 10):
if (value in row_check[i]) or (value in col_check[j]) or (value in grid_check[i // 3][j // 3]):
continue
board[i][j] = str(value)
row_check[i].add(value)
col_check[j].add(value)
grid_check[i // 3][j // 3].add(value)
if not dfs(i, j + 1, board, row_check, col_check, grid_check):
board[i][j] = '.'
row_check[i].remove(value)
col_check[j].remove(value)
grid_check[i // 3][j // 3].remove(value)
else:
return True
return False
for i in range(9):
for j in range(9):
if board[i][j] != '.':
row_check[i].add(int(board[i][j]))
col_check[j].add(int(board[i][j]))
grid_check[i // 3][j // 3].add(int(board[i][j]))
dfs(0, 0, board, row_check, col_check, grid_check)
4. 结果
image.png
