Image from Wikipedia
数独パズルを解くソルバーを Python で実装してみたので、考え方も含めてご紹介します。
きっかけは Awesome Python Newsletter で紹介されていた次の動画です。
Python の基本的な道具だけを使って数独を解く方法を順序立ててとてもわかりやすく説明しています。 programatically に数独を解いた経験のある方にとってはなんてことのないことかもしれませんが、やったことの無い方にはとても elegant でおもしろい動画だと思います。
ちなみに、今回説明する方法は上の動画の方法をきっかけ・参考にしていますが、コードの書き方・解き方は若干異なります。
数独をプログラムで解くときのポイント
おそらくここまで読み進めている方は数独がどんなものかはある程度ご存知だと思うので、数独とは何ぞやという説明は割愛します。
数独を解くアルゴリズムに関係するルールだけまとめると以下のとおりです。
- R1. 縦横 9 x 9 のマス（以下「グリッド」）のそれぞれに 1 から 9 の数字を入れられる
- R2. すべてのマスを埋めたら完成
- R3. 同じ行、同じ列、 3 x 3 のブロックに同じ数字を入れることはできない
- R4. 初期状態として、いくつかのマスに数字が入ったグリッドが与えられる
ということで、これをプログラムで解く方法を考えます。
データ構造
まずはデータ構造から。 9 x 9 のマスが必要なので、その状態を表せるデータタイプを用意します。
いちばんかんたんなのは、次のように要素が 1 - 9 の整数からなる 2 次元リスト（入れ子のリスト）を使うことです。空のセルは 0 で表します。
grid1 = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9],
]シンプルでわかりやすいですね。
ただ、これをそのまま使うよりは、ラップするデータクラスを作っておいた方が後が楽そうなので、今回はそれを用意することにします。
ROWS = COLS = 9
NUMBERS = [x for x in range(1, 9 + 1)]
class Grid:
"""数独のクイズを表すグリッド"""
_values: List[List[int]]
def __init__(self, values: List[List[int]]):
assert isinstance(values, list)
assert len(values) == ROWS
for row in values:
assert isinstance(row, list)
assert len(row) == COLS
self._values = valuesアサーションをいくつか入れておくとケアレスミスで悩むのを防げそうです。
これは次のような形で使います。
grid1 = Grid([
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9],
])これで上の R1 ・ R2 のふたつを実現できそうです。続いてアルゴリズムを考えます。
アルゴリズム
アルゴリズムの全体的な流れは次のとおりです。
- S0. パズルの状態を表すグリッドを渡される
- S1. グリッドのすべての空のセルに対して、現時点で入りうる数字をすべて洗い出す
- S2. 空のセルのうち、入りうる数字が最も少ないセルに仮に数字を入れる
- S3. S2 のグリッドを使って 1 に戻る
- S4. 空のセルがなくなったらパズルが解けたとみなす
- S5. 入りうる数字が無い空のセルが残った場合はそのルートは間違っているので終了
これを実装することで R2 ・ R3 を満たせるはずです。
S3 の部分は再帰を使って書くとよさそうです。
S1 と S2 では、空のセルの抽出、そして入りうる数字のリストアップが必要です。ここをきちんと書かないとうまく再帰が回らずに無限ループに陥ったりします。
再帰の停止条件は S4 と S5 です。
続いてこれをコードで書いていきます。
実装
まずは全体の半擬似コードを書きます。
from typing import List, Set
def main():
# グリッドを定義してから解く
grid1 = [...]
grid = Grid(grid1)
results = solve_all(grid)
for r in results:
print(r)
class Grid:
"""数独のクイズを表すグリッド"""
_values: List[List[int]]
def __init__(self, values: List[List[int]]):
assert isinstance(values, list)
assert len(values) == ROWS
for row in values:
assert isinstance(row, list)
assert len(row) == COLS
self._values = values
def solve_all(grid: Grid) -> Set:
"""指定された数独に対する解を全件返す"""
solutions = set()
def _solve(grid: Grid):
# S4. 空のセルがなくなったら正解として追加
# S1. すべてのセルに対して入りうる数字をリストアップする
# S2 + S3. 入りうち数字が最も少ないセルに仮に数字を入れて再帰
# S5. 入りうる数字がひとつも無い空のセルがある場合はそのルートは間違いなので終了
_solve(grid)
return solutions
if __name__ == '__main__':
main()これでよさそうなので実際のコードを入れていきます。
from __future__ import annotations
from pprint import pformat
from typing import List, Set, Tuple
ROWS = COLS = 9
NUMBERS = [x for x in range(1, 9 + 1)]
def main():
# グリッドを定義してから解く
grid1 = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9],
]
grid = Grid(grid1)
results = solve_all(grid)
for r in results:
print(r)
class Grid:
"""数独のクイズを表すグリッド"""
_values: List[List[int]]
def __init__(self, values: List[List[int]]):
assert isinstance(values, list)
assert len(values) == ROWS
for row in values:
assert isinstance(row, list)
assert len(row) == COLS
self._values = values
def __hash__(self):
"""hashable 化するための __hash__ 定義
- set() で利用するため
"""
return hash(''.join(str(x) for row in self._values for x in row))
def __str__(self):
"""`print()` で出力されたときの表現を定義する"""
return '{}(\n{}\n)'.format(type(self).__name__, pformat(self._values))
def solved(self) -> bool:
"""空セルがなくなったかどうかを判定する"""
all_values = [x for row in self._values for x in row]
return 0 not in all_values
def possible_numbers(self) -> List[Tuple[int, int, List[int]]]:
"""すべての空セルと入りうる数字の組み合わせを全件洗い出す"""
return [
(row, col, self._possible_numbers_for_cell(row, col))
for row, values in enumerate(self._values)
for col, x in enumerate(values)
if x == 0
]
def clone_filled(self, row, col, number) -> Grid:
"""特定のセルに指定された値が入った新しい grid を返す"""
values = [[x for x in row] for row in self._values]
values[row][col] = number
return type(self)(values)
def _possible_numbers_for_cell(self, row, col) -> List[int]:
row_numbers = [x for x in self._values[row]]
col_numbers = [row[col] for row in self._values]
block_numbers = self._block_numbers(row, col)
return [
x
for x in NUMBERS
if (x not in row_numbers)
and (x not in col_numbers)
and (x not in block_numbers)
]
def _block_numbers(self, row, col) -> List[int]:
row_start = (row // 3) * 3
col_start = (col // 3) * 3
return [
x
for row in self._values[row_start : row_start + 3]
for x in row[col_start : col_start + 3]
]
def solve_all(grid: Grid) -> Set[Grid]:
"""指定された数独に対する解を全件返す"""
solutions = set()
def _solve(grid: Grid):
# S4. 空のセルがなくなったら正解として追加
if grid.solved():
solutions.add(grid)
return
# S1. すべてのセルに対して入りうる数字をリストアップする
possible_numbers = grid.possible_numbers()
# S2 + S3. 入りうち数字が最も少ないセルに仮に数字を入れて再帰
row, col, numbers = min(possible_numbers, key=lambda x: len(x[-1]))
# S5. 入りうる数字がひとつも無い空のセルがある場合はそのルートは間違いなので終了
if not numbers:
return
for number in numbers:
next_grid = grid.clone_filled(row, col, number)
_solve(next_grid)
_solve(grid)
return solutions
if __name__ == '__main__':
main()最大のポイントは _solve() 内の再帰の部分です。
for number in numbers:
next_grid = grid.clone_filled(row, col, number)
_solve(next_grid)clone_filled() の中身は次のとおりにしています。
def clone_filled(self, row, col, number) -> Grid:
values = [[x for x in row] for row in self._values]
values[row][col] = number
return type(self)(values)Python のリストは再代入のときに参照渡しをするので、 _values を新しい Grid インスタンスと共用すると思わぬ挙動を招きかねません。そのためここでは意図して 2 次元リストを展開して別のリストを作成しています。
ちなみにここは標準ライブラリの deepcopy.deepcopy() を使うとよりシンプルに書けます。
他にも Grid クラスに特殊メソッド __hash__() や __str__() を定義する等細かなポイントはいろいろありますが、興味のある方は読んでみてください。
上のコードを Python 3.7 で実行すると次のような出力が得られます。
Grid(
[[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 2, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 1],
[7, 1, 3, 9, 2, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4, 1, 9, 6, 3, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9]]
)このパズルの場合は解はただひとつだけですが、例えば次のような空セルが多いパズルだと複数の解があるため、それが全件返されます。
grid2 = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9],
]出力結果:
Grid(
[[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 2, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 1],
[7, 1, 3, 9, 2, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4, 1, 9, 6, 3, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9]]
)
Grid(
[[3, 4, 5, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 2, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 1],
[7, 1, 3, 9, 2, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4, 1, 9, 6, 3, 5],
[5, 3, 4, 2, 8, 6, 1, 7, 9]]
)以上です。ということで Python で数独を解くサンプルでした。 冒頭に紹介した動画が非常におもしろいので興味のある方はそちらも見てみてください。