数独求解

递归与回溯

说明

给空格尝试符合行列与宫格约束的数字；遇到矛盾时回退。

分析

找到第一个空格后，枚举 1 到 9，并检查该数字是否已出现在对应行、列或 3×3 宫格。合法时暂填并递归，后续无解就恢复为空格。

图解推演

每次选一个空格，候选必须同时不在该行、该列与所属 3×3 宫中。图中的集合是一个局部候选演示：行列合并排除 1..7，宫再排除 8，剩下 9。局部唯一不等于任意初盘都有解；候选全失败必须清回点号，让上层试别的数字。

查看图表代码

适用前提与边界

示例返回找到的第一组解；实际应用还应检查初始棋盘是否已违反规则。

示例输入与调用

var board [9][9]byte
	for i, row := range []string{"534678912", "672195348", "198342567", "859761423", "426853791", "713924856", "961537284", "287419635", "345286179"} {
		copy(board[i][:], row)
	}
	board[0][0] = '.'
	SolveSudoku(&board)
	fmt.Println(string(board[0][:]))

运行输出

534678912

完整 Go 示例

package main

import "fmt"

func SolveSudoku(b *[9][9]byte) bool {
	for r := 0; r < 9; r++ {
		for c := 0; c < 9; c++ {
			if b[r][c] != '.' {
				continue
			}
			for d := byte('1'); d <= '9'; d++ {
				ok := true
				for k := 0; k < 9; k++ {
					if b[r][k] == d || b[k][c] == d || b[r/3*3+k/3][c/3*3+k%3] == d {
						ok = false
						break
					}
				}
				if ok {
					b[r][c] = d
					if SolveSudoku(b) {
						return true
					}
					b[r][c] = '.'
				}
			}
			return false
		}
	}
	return true
}

func main() {
	var board [9][9]byte
	for i, row := range []string{"534678912", "672195348", "198342567", "859761423", "426853791", "713924856", "961537284", "287419635", "345286179"} {
		copy(board[i][:], row)
	}
	board[0][0] = '.'
	SolveSudoku(&board)
	fmt.Println(string(board[0][:]))
}