数独也可以让电脑来解。最简单的办法是给空格依次试填数字,走进死胡同就退回一步重来。这种办法叫回溯法(backtracking)。

回溯法的思路

  1. 从左上角开始,依次找空格。
  2. 给这个格子依次试填 1 到 9。同一行、列、宫里已经有这个数字,就跳过。
  3. 有能填的数字就填上,走向下一个空格。
  4. 如果走到一个哪个数字都填不了的格子,就退回上一个格子,试下一个数字。
  5. 没有空格了,就完成了。

人解题时要避免乱猜,但电脑填错了可以马上退回去,所以哪怕一个个硬试,也能很快得出答案。

用 Python 来写

盘面用一个列表表示,把81个数字从左上角起,先向右、再向下排开(0 表示空格)。第 i 个格子,i÷9 的商是行,余数是列。

def can_place(grid, r, c, d):
    # 同一行、列、宫里没有 d 才能放
    for k in range(9):
        if grid[r * 9 + k] == d or grid[k * 9 + c] == d:
            return False
    br, bc = r // 3 * 3, c // 3 * 3
    for rr in range(br, br + 3):
        for cc in range(bc, bc + 3):
            if grid[rr * 9 + cc] == d:
                return False
    return True


def solve(grid):
    # 找到空格,依次试填 1~9。走进死胡同就退回去
    for i in range(81):
        if grid[i] == 0:
            r, c = divmod(i, 9)
            for d in range(1, 10):
                if can_place(grid, r, c, d):
                    grid[i] = d
                    if solve(grid):
                        return True
                    grid[i] = 0
            return False
    return True


puzzle = "3..5..182.....2.9.8.2.91.4...52.9..6724.1.8396..4.85...5.12.9.7.3.7.....267..4..8"
grid = [0 if ch == "." else int(ch) for ch in puzzle]
solve(grid)
for r in range(9):
    print(" ".join(str(v) for v in grid[r * 9 : r * 9 + 9]))

运行后会像下面这样显示答案。题目是 NumberPlace 里 ★1 的一道题。

3 4 9 5 6 7 1 8 2
5 1 6 8 4 2 7 9 3
8 7 2 3 9 1 6 4 5
1 8 5 2 3 9 4 7 6
7 2 4 6 1 5 8 3 9
6 9 3 4 7 8 5 2 1
4 5 8 1 2 3 9 6 7
9 3 1 7 8 6 2 5 4
2 6 7 9 5 4 3 1 8

数一数有几个解

出题的时候,会想确认答案是不是只有一个(为什么答案只有一个)。把上面的程序稍微改一下,找到答案后不停下来,而是继续往下数,就能知道解的个数。找到2个的时候,就已经知道“不止一个解”了,所以到这里就可以中止。

def count_solutions(grid, limit=2):
    # 找到 limit 个解就停下(找到2个就知道“不止一个解”)
    for i in range(81):
        if grid[i] == 0:
            r, c = divmod(i, 9)
            found = 0
            for d in range(1, 10):
                if can_place(grid, r, c, d):
                    grid[i] = d
                    found += count_solutions(grid, limit - found)
                    grid[i] = 0
                    if found >= limit:
                        break
            return found
    return 1


grid = [0 if ch == "." else int(ch) for ch in puzzle]
print(count_solutions(grid))

上面的 ★1 题会显示 1,有两个解的题会显示 2。

加快速度的办法

与其从左上角依次试,不如从能填的数字最少的格子开始试,速度会快很多。从只有一个候选数的格子开始填,几乎不用退回去。NumberPlace 确认解的个数时,也是按这个顺序试的。

和人一样用技巧来解

回溯法又快又可靠,但它不会告诉你“为什么这里要填这个数字”。NumberPlace 的“提示”和题目难度的判定,用的是另一种办法。

  1. 给每个空格记下能填的数字(候选数)。
  2. 从简单的技巧开始,找能用的。
  3. 往前走一步后,再从最简单的技巧重新找起。

技巧从“只有这里能填”“只能填这个数字”,到区块摒除、数对、X-Wing、XY-Wing、Swordfish,共15种,按由易到难排列(数独的解法)。因为和人解题的顺序一样,所以能知道用了哪些技巧,由此来决定 ★,也能在提示里讲清理由。