はじめに
この連載は、主に制約プログラミング（以下CP）の未経験者・入門者の方を対象に、親しみのあるパズルを解くプログラムを例に、CPの考え方をお伝えしようとするものです。
連載目次
連載は以下の記事に分かれています。既にCPになじみのある方は適宜読み飛ばしてください。
- はじめての制約プログラミング
- 【本記事】動作環境を構築し、簡単なプログラムでCPの考え方を解説します
- 正解がいくつもある問題
- コールバックを実装してすべての解を出力する方法を解説します
- ナンプレ（数独）を解く
- おそらく最もCPが適用しやすいパズル「ナンプレ」を解いてみます
- お絵描きロジック 構想編
- お絵描きロジックを解くプログラムの全体像を解説します（この時点では解けません）
- お絵描きロジック 解法編
- お絵描きロジックを解けるようサブプログラムを書いて実際に解いてみます
本連載が皆様のCPライフ（？）の一助となるべく頑張って書いてまいります。
ご意見・ご感想、また内容に誤り等を発見された場合には是非お知らせください。
はじめてのCP
お絵描きロジックを解くプログラムを書くとしたら、最初に何を考えますか？
手続き型プログラミング経験者の多くは、真っ先にどんなアルゴリズムにするかを考えるのではないでしょうか。
CPでは個々の問題を解くアルゴリズムをその都度考えません。その代わりに、世界中の研究者やエンジニアの成果が詰まった“ソルバー”（Solver - 解く者）に問題を伝えて解いてもらうのです。
この説明ではおそらくピンとこないと思いますので、簡単なプログラムでその方法を見ていきましょう。
記事の目標
- PythonとOR-ToolsでCPの動作環境を構築できる
- CPの考え方を理解できる
動作環境
この連載ではPythonとOR-Toolsを使ってCPの動作を見ていきます。いずれもオープンソースで提供されていますので、まずはPythonをインストールしてください。執筆時点でOR-Toolsの利用に必要なPythonのバージョンは3.8以降です。
Pythonが動作する環境で、以下のコマンドを実行すると、OR-Toolsをインストールできます。
python -m pip install ortools
OR-Toolsについて詳しく知りたい方は、本家Google for Developersを参照してください。
整数のリストを作るプログラム
1から10までの整数が順に入ったリストを作るプログラムを考えます。
Pythonではlist(range(1, 11))と書けますが、これでは手続きもへったくれもありませんので、敢えて手続き型っぽく書くとこんな感じでしょうか。
numbers = []
for x in range(10):
numbers += [x + 1]
print(numbers) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
これをCPで書くとこうなります。
from ortools.sat.python import cp_model
# モデルの初期化
model = cp_model.CpModel()
# 決定変数
numbers = [model.NewIntVar(1, 10, f"numbers_{i}") for i in range(10)]
# 制約
for i in range(9):
model.Add(numbers[i + 1] == numbers[i] + 1)
# ソルバーで解く
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status in {cp_model.FEASIBLE, cp_model.OPTIMAL}:
print('解けました')
print([solver.Value(numbers[i]) for i in range(10)])
else:
print('解けませんでした')
以下、順に解説していきます。
モデル
OR-Toolsでは、解きたい問題をモデルと呼ばれるオブジェクトを使って定義します。
モデルには定義する問題の種類に対応するいくつものクラスがあり、制約充足問題を定義するためのクラスがCpModelです。
from ortools.sat.python import cp_model
# モデルの初期化
model = cp_model.CpModel()
OR-Toolsは、最適化問題や制約充足問題を解くためのモデルとソルバーを集めたライブラリで、制約充足問題を定義してソルバーで解く手法がCP（制約プログラミング）です。
決定変数
ソルバーが見つけた解を格納するための変数が決定変数です。
# 決定変数
numbers = [model.NewIntVar(1, 10, f"numbers_{i}") for i in range(10)]
model.NewIntVar(lb, ub, name)は、lbからubまでの範囲の値を持つnameという名前の整数型の決定変数を作って返します。このプログラムではそれを10個作り、リストにしてnumbersに保持しています。
制約
解（つまり決定変数）が満たすべき制約をモデルに追加していきます。
# 制約
for i in range(9):
model.Add(numbers[i + 1] == numbers[i] + 1)
ここでは、「リストの2番目以降の決定変数は、ひとつ前の決定変数に1を加えたものと等しい」という制約を追加しています。
ソルバー
決定変数と制約がすべて定義できたので、モデルをソルバーに渡して解かせます。
# ソルバーで解く
solver = cp_model.CpSolver()
status = solver.Solve(model)
CpModelに対応するソルバーがCpSolverクラスです。
ここではCpSolverのSolveメソッドにモデルを渡して解いています。
解を表示する
CpSolverのSolveメソッドは、すべての制約を満たす解がみつかるとcp_model.FEASIBLEかcp_model.OPTIMALを返します。
if status in {cp_model.FEASIBLE, cp_model.OPTIMAL}:
print('解けました')
print([solver.Value(numbers[i]) for i in range(10)])
else:
print('解けませんでした')
問題が解けたら、solver.Value()で決定変数の値をソルバーから取得します。ここではリストに格納して表示しています。
以上で1から10までの整数が順に格納されたリストを表示することができました。
解けました
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
アルゴリズムがないプログラム
ここでもう一度プログラムを見返してみてください。このプログラムには、1から10までの整数を順にリストに格納する手順、つまりアルゴリズムが書かれていません。
一見すると制約を追加する部分がアルゴリズムに見えなくもありませんが、ここを以下のように書き換えても結果は変わりません。制約の順番はどうでも良い、つまりこの部分も“手順”ではない訳です。
# 制約
- for i in range(9):
- model.Add(numbers[i + 1] == numbers[i] + 1)
+ model.Add(numbers[4] == numbers[3] + 1)
+ model.Add(numbers[2] == numbers[1] + 1)
+ model.Add(numbers[3] == numbers[2] + 1)
+ model.Add(numbers[8] == numbers[7] + 1)
+ model.Add(numbers[1] == numbers[0] + 1)
+ model.Add(numbers[5] == numbers[4] + 1)
+ model.Add(numbers[9] == numbers[8] + 1)
+ model.Add(numbers[6] == numbers[5] + 1)
+ model.Add(numbers[7] == numbers[6] + 1)
でも私たちは「すべてのプログラムにはアルゴリズムがある」と教えられてきました。だとすると、このプログラムのアルゴリズムはどこに行ったのでしょうか。
答えはソルバーの中です。ソルバーは多くの研究者や腕利きのエンジニアが生み出した探索アルゴリズムのかたまりです。もちろん限界はありますが、多くの場合、渡された問題に応じて難なく解を見つけ出してしまいます。
そこで…
お絵描きロジックを解くアルゴリズムを自分で考えなくても、CPで解いてもらえるんじゃね？ というのがこの連載の肝、というわけです。
連載の目標
- CPでパズル（ナンプレ、お絵描きロジック）を解いてみる
- ビジネス等へのCPの応用を検討できるようになる
次回は
ナンプレやお絵描きロジックで遊んでいると、たまに出題ミスで正解が複数あるケースがあります。
制約充足問題でも複数の解があるのはよくあることですが、OR-ToolsのCPソルバーですべての解を求めるにはひと手間かかりますので、次回はすべての解を表示する方法を解説します。