ナンプレ(数独)は、コンピューターに解かせることもできます。いちばん簡単なのは、空いたマスに数字を順に試し、行き詰まったら1つ戻ってやり直す方法です。この方法をバックトラック(後戻り法)と呼びます。
バックトラックの考え方
- 左上から順に、空いたマスを探す。
- そのマスに、1から9を順に入れてみる。同じ行・列・箱に同じ数字があれば、その数字は飛ばす。
- 入れられる数字があれば入れて、次の空きマスへ進む。
- どの数字も入れられないマスに来たら、1つ前のマスに戻って、次の数字を試す。
- 空きマスがなくなったら、完成。
人が解くときには当てずっぽうは避けますが、コンピューターは間違えたらすぐ戻れるので、片っぱしから試してもすぐに答えにたどりつきます。
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手進めたら、またいちばんやさしい手筋から探し直す。
手筋は、「ここにしか入らない」「この数字しか入らない」から、候補の限定、ペア、X-Wing、XY-Wing、ソードフィッシュまで、15種類をやさしい順に並べています(ナンプレの解き方)。人が解くのと同じ順番で進むので、どの手筋が要ったかが分かり、それで★を決めたり、ひらめきで理由を見せたりできます。
