はじめに
この連載は、主に制約プログラミング（以下CP）の未経験者・入門者の方を対象に、親しみのあるパズルを解くプログラムを例に、CPの考え方をお伝えしようとするものです。
この記事の前提
- PythonとOR-Toolsの基礎知識と動作環境
- 複数の解を取得する制約プログラムの書き方と考え方の理解
本連載の第2回「正解がいくつもある問題を解く」読了相当以上の方向けの内容です
連載目次
連載は以下の記事に分かれています。既にCPになじみのある方は適宜読み飛ばしてください。
- はじめての制約プログラミング
- 動作環境を構築し、簡単なプログラムでCPの考え方を解説します
- 正解がいくつもある問題
- コールバックを実装してすべての解を出力する方法を解説します
- ナンプレ（数独）
- おそらく最もCPが適用しやすいパズル「ナンプレ」を解いてみます
- お絵描きロジック（最終回）
- お絵描きロジックをCPを使って解いてみます
ご意見・ご感想、また内容に誤り等を発見された場合には是非お知らせください。
ナンプレとは
英語ではNumber Place、日本では数独とも呼ばれている、9×9のマス目を1～9の数字で埋めていくパズルです。
マスの一部には最初から数字が書かれていて、残りのマスを後述のルールに違反しないようにすべて埋めるのがゴールです。
ナンプレのルール
- 各行（ヨコ）で数字が重複してはならない
- 各列（タテ）で数字が重複してはならない
- 9個ある3×3の各ブロックで数字が重複してはならない
行・列・ブロックともマスの数は9個で数字は1から9までなので、各行・列・ブロックにはすべての数字が1個ずつ入ることになります。
各行で数字が重複してはならない
3行目を例に図示すると、赤枠内に同じ数字が2回現れてはいけません。
すべての行が上図の3行目のようにならなくてはいけません。
各列で数字が重複してはならない
2列目を例に図示すると、赤枠内に同じ数字が2回現れてはいけません。
すべての列が上図の2列目のようにならなくてはいけません。
各ブロックで数字が重複してはならない
下図の色分けした各ブロック内で、同じ数字が2回現れてはいけません。
すべてのブロックが中央のブロックのようにならなくてはいけません。
ナンプレを解くプログラム
早速CPでナンプレを解いてみます。モデルの初期化はいつも通りなので、決定変数から解説します。
決定変数
ナンプレは、9×9＝81個のマスがすべて1から9までの数字で埋まれば完成なので、整数の2次元のリストを決定変数にします。
# 決定変数
grid = [[model.NewIntVar(1, 9, f"cell_{x}_{y}") for x in range(9)] for y in range(9)]
整数型の決定変数を作るNewIntVar(lb, ub, name)には、決定変数がとりうる値の下限(lb)と上限(ub)を指定します。
制約
ナンプレのルール
先述のルールを制約として追加します。
# 制約（ナンプレのルール）
for row in grid: # 行
model.AddAllDifferent(row)
for column in zip(*grid): # 列
model.AddAllDifferent(column)
for by in range(3):
for bx in range(3):
model.AddAllDifferent([
grid[by * 3 + y][bx * 3 + x] for y in range(3) for x in range(3)
])
AddAllDifferent()で決定変数の値が重複しないという制約を追加しています。
for column in zip(*grid):では、*gridで二次元リストを9個のリストにアンパックし、zip()でそれぞれの対応する要素を組にして取り出し、列を作っています。
最初から書かれている数字
ナンプレのルールは書けたので、次に最初から決まっている数字（既定値）をモデルに定義します。既定値も制約として追加します。
# 制約（既定の値）
given = [
[0,0,8,0,0,9,2,0,0],
[0,0,0,0,1,0,0,0,0],
[1,0,0,0,0,3,9,0,4],
[0,0,2,0,0,7,0,4,0],
[0,4,7,0,0,0,0,0,0],
[0,3,0,1,4,0,0,0,6],
[0,0,0,0,9,0,1,0,0],
[0,0,5,0,0,0,4,8,3],
[0,2,0,3,0,0,5,7,0]
]
for y in range(9):
for x in range(9):
if given[y][x] != 0:
model.Add(grid[y][x] == given[y][x])
ここで重要なのは、決定変数の値は直接指定したり変更したりできない点です。決定変数はソルバーが解を探すときに値を入れる変数です。ユーザプログラム側に値を決める権利はないので、代わりに「この値と等しい」という制約を追加して値をコントロールします。
重要：決定変数とは、値をソルバーが決める変数
ソルバーで解く
以上で決定変数と制約が定義できたので、ソルバーに解を探してもらって、見つかった解を表示します。
以下、完成したプログラムです。（第2回で作ったcp_solution_collector.pyをimportしています）
from ortools.sat.python import cp_model
from cp_solution_collector import CpSolutionCollector
# モデルの初期化
model = cp_model.CpModel()
# 決定変数
grid = [[model.NewIntVar(1, 9, f"cell_{x}_{y}") for x in range(9)] for y in range(9)]
# 制約（ナンプレのルール）
for row in grid: # 行
model.AddAllDifferent(row)
for column in zip(*grid): # 列
model.AddAllDifferent(column)
for by in range(3):
for bx in range(3):
model.AddAllDifferent([
grid[by * 3 + y][bx * 3 + x] for y in range(3) for x in range(3)
])
# 制約（既定の値）
given = [
[0,0,8,0,0,9,2,0,0],
[0,0,0,0,1,0,0,0,0],
[1,0,0,0,0,3,9,0,4],
[0,0,2,0,0,7,0,4,0],
[0,4,7,0,0,0,0,0,0],
[0,3,0,1,4,0,0,0,6],
[0,0,0,0,9,0,1,0,0],
[0,0,5,0,0,0,4,8,3],
[0,2,0,3,0,0,5,7,0]
]
for y in range(9):
for x in range(9):
if given[y][x] != 0:
model.Add(grid[y][x] == given[y][x])
# ソルバーで解く
solver = cp_model.CpSolver()
collector = CpSolutionCollector(grid)
status = solver.SearchForAllSolutions(model, collector)
if status in {cp_model.FEASIBLE, cp_model.OPTIMAL}:
print('解けました')
solutions = collector.solutions
for i, solution in enumerate(solutions):
print("解", i + 1)
for row in solution:
print(*row)
else:
print('解けませんでした')
あっという間にナンプレを解くことができるようになりました。
解けました
解 1
3 5 8 4 6 9 2 1 7
2 9 4 7 1 5 6 3 8
1 7 6 8 2 3 9 5 4
6 1 2 9 3 7 8 4 5
8 4 7 6 5 2 3 9 1
5 3 9 1 4 8 7 2 6
7 8 3 5 9 4 1 6 2
9 6 5 2 7 1 4 8 3
4 2 1 3 8 6 5 7 9
次回は
今回、やっとゴールがある問題を解くプログラムをお見せできました。IT技術者が取り組んでいる様々な問題（ビジネス等）に応用できる可能性が伝わっていれば幸いです。
例えば、勤務シフト表の作成は、労働に関する法律や規則の制約を満たし、スタッフの休日の希望にもできるだけ応えようとするので、CPが得意とするタイプの問題だと思います。
思い出していただきたいのは、第1回で説明した通りアルゴリズムを書いていないことです。複雑な問題を解くアルゴリズムを考えなくても、ほしい答えの構造（決定変数）と制約を書くだけで解が得られる点がCPの最大の特徴です。
連載の目標
- CPでパズル（ナンプレ、お絵描きロジック）を解いてみる
- ビジネス等へのCPの応用を検討できるようになる
次回はいよいよ、お絵描きロジックに取り組んでみたいと思います。