概要
大学の宿題でpython-constraintを使って制約充足問題（CSP）の代表ともいえる数独を解くプログラムを書かされました。
超マイナーなライブラリっぽく解説記事もあんまりなかったので自分の備忘録がてら記事にしてみます。
python-constraintとは
pypiに上がってるパッケージです。制約充足問題を解くためのライブラリ。
最終更新が2018年とちょっと古めではありますが、制約充足問題の定番として（特にアカデミックでは）人気のようです。
サンプルコード
import constraint
def solver(sudoku_problem):
all_cells = [(r, c) for r in range(9) for c in range(9)]
possible_val = [i for i in range(1, 9 + 1)]
p = constraint.Problem(constraint.RecursiveBacktrackingSolver())
p.addVariables(all_cells, possible_val)
# 既に埋まっているマスを登録
for idx_r, r in enumerate(sudoku_problem):
for idx_c, c in enumerate(r):
if sudoku_problem[idx_r][idx_c] != 0:
p.addConstraint(lambda v, num=sudoku_problem[idx_r][idx_c]: v == num, [(idx_r, idx_c)])
# 行と列それぞれに対して、 `AllDifferentConstraint` の制約を付ける
group_max = sum(range(9 + 1))
for i in range(9):
row = [(i, l) for l in range(9)]
column = [(l, i) for l in range(9)]
p.addConstraint(constraint.AllDifferentConstraint(), row)
p.addConstraint(constraint.AllDifferentConstraint(), column)
# 3x3の9マス（ボックスと呼びます）に対して、 `AllDifferentConstraint` の制約を付ける
box_range = [(0, 3), (3, 6), (6, 9)]
for i in box_range:
for l in box_range:
box = [(a, b) for a in range(*i) for b in range(*l)]
p.addConstraint(constraint.AllDifferentConstraint(), box)
return p.getSolution()
インプットの sudoku_problem は既に埋められている数字のリストです。
以下のような形式を想定しています。
０はそのマスが空であることを意味します。
example = [
[1, 0, 7, 2, 4, 6, 0, 9, 3],
[2, 3, 0, 7, 8, 9, 5, 0, 1],
[9, 4, 0, 0, 1, 3, 7, 0, 2],
[3, 6, 9, 0, 7, 2, 1, 5, 0],
[5, 7, 1, 0, 0, 8, 2, 3, 0],
[8, 2, 4, 3, 0, 1, 9, 7, 6],
[0, 1, 5, 6, 0, 0, 3, 8, 9],
[0, 8, 3, 1, 9, 0, 4, 2, 7],
[7, 0, 2, 8, 3, 0, 0, 1, 5]
]
解説
まず初期設定。
all_cells = [(r, c) for r in range(9) for c in range(9)]
possible_val = [i for i in range(1, 9 + 1)]
p = constraint.Problem(constraint.RecursiveBacktrackingSolver())
p.addVariables(all_cells, possible_val)
最初の４行で問題の定義を行います。
この時点では、セル座標は順序なく all_cells の中でただ一列に並んでいるイメージです。
possible_val は使える値を全て定義します。ここでは1~9の数字ですね。
それを constraint.Problem に登録することで、初期設定は完了です。
ちなみに、 constraint.RecursiveBacktrackingSolver() を使っているのは、初期値のsolverだとものすごく時間がかかるためです。バックトラッキングはさすがの早さです。
つぎにそれぞれの制約を設定します。
数独パズルは以下の制約を持ちます。これをコード上で再現します。
- 既に埋められているマスの数字の変更はできない（数字が固定）
- 行の中で１～９の数字が重複してはいけない
- 列の中で１～９の数字が重複してはいけない
- ボックス（3x3、合計９マスのグループ）の中で１～９の数字が重複してはいけない
それぞれ解説します。
1. 既に埋められているマスの数字の変更はできない（数字が固定）
for idx_r, r in enumerate(sudoku_problem):
for idx_c, c in enumerate(r):
if sudoku_problem[idx_r][idx_c] != 0:
p.addConstraint(lambda v, num=sudoku_problem[idx_r][idx_c]: v == num, [(idx_r, idx_c)])
この制約の手がかりはインプットの問題です。
マスが空ではない（＝０以外の）場合、 addConstraint で制約を追加します。
このパッケージでは制約はlistに対して追加されるので、マス座標のtupleが１つだけ入ったlistを作って、そこに特定の数字が制約されるようにします。
2 & 3 & 4. 行・列・ボックスの中で１～９の数字が重複してはいけない
# 行と列それぞれに対して、 `AllDifferentConstraint` の制約を付ける
group_max = sum(range(9 + 1))
for i in range(9):
row = [(i, l) for l in range(9)]
column = [(l, i) for l in range(9)]
p.addConstraint(constraint.AllDifferentConstraint(), row)
p.addConstraint(constraint.AllDifferentConstraint(), column)
# 3x3の9マス（ボックスと呼びます）に対して、 `AllDifferentConstraint` の制約を付ける
box_range = [(0, 3), (3, 6), (6, 9)]
for i in box_range:
for l in box_range:
box = [(a, b) for a in range(*i) for b in range(*l)]
p.addConstraint(constraint.AllDifferentConstraint(), box)
前述のとおり、制約はlistに対してかけられるので、それぞれ対象範囲の座標のlistさえ作れれば勝ちです。
constraintはパッケージ内に予め定義されている constraint.AllDifferentConstraint() を使います。
名前の通り、全てが別の値になるように埋める条件を設定します。
解決
p.getSolution()
getSolution()をすることで解答が出力されます。
出力は最初の p.addVariables() で第一引数に登録した形式で出力されるので、この場合ちょっとみずらいです。
適当に整形して読みやすくします。
def _convert_to_list(s):
t = {i: {} for i in range(9)}
for k, v in s.items():
t[k[0]][k[1]] = v
result_table = []
for k, l in t.items():
result_table.append([l[i] for i in range(9)])
return result_table
そしたらだいたいこんな感じで回答が出てきます。うまくいってそうです。
[
[1, 5, 7, 2, 4, 6, 8, 9, 3],
[2, 3, 6, 7, 8, 9, 5, 4, 1],
[9, 4, 8, 5, 1, 3, 7, 6, 2],
[3, 6, 9, 4, 7, 2, 1, 5, 8],
[5, 7, 1, 9, 6, 8, 2, 3, 4],
[8, 2, 4, 3, 5, 1, 9, 7, 6],
[4, 1, 5, 6, 2, 7, 3, 8, 9],
[6, 8, 3, 1, 9, 5, 4, 2, 7],
[7, 9, 2, 8, 3, 4, 6, 1, 5]
]
おわりに
CSPを簡単につくれるのでなかなかたのしいです。
CSPが日常で必要になる場面ってあんまりなさそうですが必要になったら使ってみてください。
公式ドキュメントこちら