數獨也可以交給電腦來解。最簡單的方法是:在空格依序試填數字,走不通就退回上一步重來。這種方法稱為回溯法。

回溯法的想法

  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

數一數有幾個解

出題的時候,會想確認答案是不是只有 1 個(答案只有 1 個的理由)。只要把上面的程式稍微改一下,找到答案也不停下來、繼續數下去,就能知道解的數量。找到 2 個解的時候,就已經知道「不只 1 個」,所以在那裡停止。

def count_solutions(grid, limit=2):
    # 找到 limit 個解就停止(找到 2 個就知道「不只 1 個」)
    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。

讓它更快的訣竅

與其從左上角依序試填,不如從能填的數字最少的格子開始試,速度會大幅提升。從候選數只有 1 個的格子開始填,幾乎不需要退回重來。「NumberPlace」確認解的數量時,也是照這個順序試的。

用和人類一樣的技巧解題

回溯法又快又確實,但不會告訴你「為什麼那裡要填那個數字」。「NumberPlace」的「提示」和題目難度的判定,用的是另一種方法。

  1. 為每個空格記下能填的數字(候選數)。
  2. 從簡單的技巧開始,找出能用的。
  3. 往前進一步後,再從最簡單的技巧重新找起。

技巧從「只有這裡能填」「只能填這個數字」,到區塊摒除、數對、X-Wing、XY-Wing、Swordfish,共有 15 種,依由易到難排列(數獨的解法)。因為是照人類解題的順序進行,所以能知道用到了哪些技巧,再據此決定★的數量,或在提示裡說明理由。