ナンプレ(数独)は、コンピューターに解かせることもできます。いちばん簡単なのは、空いたマスに数字を順に試し、行き詰まったら1つ戻ってやり直す方法です。この方法をバックトラック(後戻り法)と呼びます。

バックトラックの考え方

  1. 左上から順に、空いたマスを探す。
  2. そのマスに、1から9を順に入れてみる。同じ行・列・箱に同じ数字があれば、その数字は飛ばす。
  3. 入れられる数字があれば入れて、次の空きマスへ進む。
  4. どの数字も入れられないマスに来たら、1つ前のマスに戻って、次の数字を試す。
  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]))

動かすと、次のように答えが表示されます。問題はアプリ「ナンプレ」の★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つある問題では2が表示されます。

速くする工夫

左上から順に試すかわりに、入れられる数字がいちばん少ないマスから試すと、ぐんと速くなります。候補が1つしかないマスから埋めていけば、ほとんど後戻りせずに済むからです。アプリ「ナンプレ」で答えの数を確かめるときも、この順番で試しています。

人と同じ手筋で解く方法

バックトラックは速く確実ですが、「なぜそこにその数字が入るのか」は教えてくれません。アプリ「ナンプレ」の「ひらめき」や問題の難しさの判定には、もう1つの方法を使っています。

  1. 空きマスごとに、入れられる数字(候補)を持っておく。
  2. やさしい手筋から順に、使えるものを探す。
  3. 1手進めたら、またいちばんやさしい手筋から探し直す。

手筋は、「ここにしか入らない」「この数字しか入らない」から、候補の限定、ペア、X-Wing、XY-Wing、ソードフィッシュまで、15種類をやさしい順に並べています(ナンプレの解き方)。人が解くのと同じ順番で進むので、どの手筋が要ったかが分かり、それで★を決めたり、ひらめきで理由を見せたりできます。