解数独（Sudoku Solver）
📌 定义
编写一个程序，通过填充空格来解决数独问题。数独的解法需遵循如下规则：
- 数字 1-9 在每一行只能出现一次
- 数字 1-9 在每一列只能出现一次
- 数字 1-9 在每一个 3×3 宫内只能出现一次
空白格用 '.' 表示。
示例:
输入:
[["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"]]
核心思路
使用回溯算法逐个填充空格：
- 选择：在空格中尝试填入 1-9
- 约束：检查是否满足数独规则
- 探索：递归填充下一个空格
- 撤销：如果无解，回溯尝试其他数字
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(9^m) | m是空格数 |
| 空间复杂度 | O(1) | 原地修改 |
Go 代码
Go 实现
func solveSudoku(board [][]byte) {
backtrack(board)
}
func backtrack(board [][]byte) bool {
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if board[i][j] != '.' {
continue
}
for num := byte('1'); num <= '9'; num++ {
if isValid(board, i, j, num) {
board[i][j] = num
if backtrack(board) {
return true
}
board[i][j] = '.'
}
}
return false
}
}
return true
}
func isValid(board [][]byte, row, col int, num byte) bool {
for i := 0; i < 9; i++ {
if board[row][i] == num {
return false
}
if board[i][col] == num {
return false
}
boxRow := (row/3)*3 + i/3
boxCol := (col/3)*3 + i%3
if board[boxRow][boxCol] == num {
return false
}
}
return true
}思路展开
约束检查详解
检查(4,4)位置是否可以填5:
1. 检查第4行:
[4,.,.,8,.,3,.,.,1]
没有5 ✓
2. 检查第4列:
[7,9,.,6,.,2,.,1,8]
没有5 ✓
3. 检查中间3×3宫格:
[.,.,.]
[8,.,3]
[.,2,.]
没有5 ✓
结果: 可以填5