はじめに
この連載は、主に制約プログラミング（以下CP）の未経験者・入門者の方を対象に、親しみのあるパズルを解くプログラムを例に、CPの考え方をお伝えしようとするものです。
この記事の前提
- PythonとOR-Toolsの基礎知識と動作環境
- ひとつの解を出力する制約プログラムの書き方と考え方の理解
本連載の第1回「はじめての制約プログラミング」読了相当以上の方向けの内容です
連載目次
連載は以下の記事に分かれています。既にCPになじみのある方は適宜読み飛ばしてください。
- はじめての制約プログラミング
- 動作環境を構築し、簡単なプログラムでCPの考え方を解説します
- 正解がいくつもある問題
- 【本記事】コールバックを実装してすべての解を出力する方法を解説します
- ナンプレ（数独）を解く
- おそらく最もCPが適用しやすいパズル「ナンプレ」を解いてみます
- お絵描きロジック 構想編
- お絵描きロジックを解くプログラムの全体像を解説します（この時点では解けません）
- お絵描きロジック 解法編
- お絵描きロジックを解けるようサブプログラムを書いて実際に解いてみます
ご意見・ご感想、また内容に誤り等を発見された場合には是非お知らせください。
正解がいくつもある問題
制約充足問題では、すべての制約を満たす解が複数あることが珍しくありません。
例えば前回取り上げた「整数が順に1ずつ増えていくリストを作る」問題では、整数の範囲を1～10のまま、リストの要素数を9個にすると、下のふたつのリストはどちらもすべての制約を満たします。
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[2, 3, 4, 5, 6, 7, 8, 9, 10]
コールバック
OR-ToolsのCPソルバーで複数の解を処理するには、ソルバーからコールバックされるクラスを用意します。
Google for Developersのドキュメントでは、コールバックを受け取るクラスを「ソリューションプリンタ」と呼んでいますが、これはサンプルのコールバックが解を表示しているからです。
ソルバーの身になって考えれば、解をひとつ見つける度に処理を呼び元にリターンすると、次の解を探すには途中になっている探索を復旧しなくてはならず大変です。
解を見つけたらコールバックを呼び出す仕組みは、コールバックから処理が返ればそのまま探索の続きができるので合理的です。
すべての解を表示する
まずはGoogle for Developersと同じようにソリューションプリンタを実装してみましょう。
from ortools.sat.python import cp_model
"""
ソリューションプリンタ
"""
class SolutionPrinter(cp_model.CpSolverSolutionCallback):
def __init__(self, variables):
super().__init__()
self.__variables = variables
def on_solution_callback(self):
print([self.Value(var) for var in self.__variables])
"""
メイン
"""
# モデルの初期化
model = cp_model.CpModel()
# 決定変数
numbers = [model.NewIntVar(1, 10, f"numbers_{i}") for i in range(9)]
# 制約
for i in range(8):
model.Add(numbers[i + 1] == numbers[i] + 1)
# ソルバーで解く
solver = cp_model.CpSolver()
printer = SolutionPrinter(numbers)
status = solver.SearchForAllSolutions(model, printer)
if status in {cp_model.FEASIBLE, cp_model.OPTIMAL}:
print('解けました')
else:
print('解けませんでした')
実行してみましょう。
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[2, 3, 4, 5, 6, 7, 8, 9, 10]
解けました
ソリューションプリンタ
ソルバーからコールバックを受け取るには、cp_model.CpSolverSolutionCallbackを継承したクラスを用意します。
class SolutionPrinter(cp_model.CpSolverSolutionCallback):
def __init__(self, variables):
super().__init__()
self.__variables = variables
def on_solution_callback(self):
print([self.Value(var) for var in self.__variables])
__init__で表示すべき決定変数を受け取り、on_solution_callbackでその値を表示しています。
このプログラムでは、受け取るのが決定変数のリストなので、値もリスト化して表示しています。
Google for Developerでは、__init__の1行目はcp_model.CpSolverSolutionCallback.__init__(self)と書かれていますが、多重継承した場合に違いがあるため、筆者はsuper().__init__()と書くようにしています。
ソルバーの呼び出し
すべての解を求めるには、ソルバーにコールバックを受け取るオブジェクトを渡します。
# ソルバーで解く
solver = cp_model.CpSolver()
printer = SolutionPrinter(numbers)
status = solver.SearchForAllSolutions(model, printer)
最後の1行は以下のように書くこともできます。
solver.parameters.enumerate_all_solutions = True
status = solver.Solve(model, printer)
すべての解を保持する
連載の後半で扱うお絵描きロジックでは、複数の解を保持して再利用する場面があります。ビジネス等にCPを応用することを考えても、解を再利用したくなるケースは多いと思います。
そこでここでは、コールバックを受け取るクラスで解を保持するように書き換えてみます。
ソリューションコレクタ
"""
ソリューションコレクタ
"""
class SolutionCollector(cp_model.CpSolverSolutionCallback):
def __init__(self, variables):
super().__init__()
self.__variables = variables
self.__solutions = [] # 解のリスト
def on_solution_callback(self):
self.__solutions.append([self.Value(var) for var in self.__variables])
@property
def solutions(self):
return self.__solutions
イニシャライザで解のリストを初期化し、on_solution_callbackでは解をprintする代わりにリストにappendしています。
solutionsプロパティで解のリストを外部に公開して、ソルバーの呼び出し元がすべての解を取得できるようにしています。
ソルバーの呼び出しと解の取得
呼び出し側は以下のように変更しました。
# ソルバーで解く
solver = cp_model.CpSolver()
collector = SolutionCollector(numbers)
status = solver.SearchForAllSolutions(model, collector)
if status in {cp_model.FEASIBLE, cp_model.OPTIMAL}:
print('解けました')
print(collector.solutions)
else:
print('解けませんでした')
実行すると以下のように表示されます。
解けました
[[1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 3, 4, 5, 6, 7, 8, 9, 10]]
汎用ソリューションコレクタ
本節は専らpythonのプログラムの再利用の話になります。CPの学習に必要な内容ではありませんので、区別してお読みいただければ幸いです。
先述の通り、この連載の後半でもソリューションコレクタを使います。
CPを応用する多くの場合に必要になるはずですが、その都度ソリューションコレクタを書くのは面倒です。
ところがCPでは、解くべき問題が変われば、決定変数の数や型、構造が変わります。
ソリューションコレクタには解を保持すべき決定変数を渡さなくてはならないので、渡された決定変数と同じ構造で解を保持するソリューションコレクタを書いてみました。
from ortools.sat.python import cp_model
"""
汎用ソリューションコレクタ for CP-SAT
"""
class CpSolutionCollector(cp_model.CpSolverSolutionCallback):
def __init__(self, *variable):
super().__init__()
self.__variable = variable[0] if len(variable) == 1 else tuple(variable)
self.__solutions = [] # 解のリスト
def on_solution_callback(self):
self.__solutions.append(self.get_value(self.__variable))
def get_value(self, variable): # 同じ構造で値を返す
if isinstance(variable, list):
return [self.get_value(var) for var in variable]
elif isinstance(variable, tuple):
return tuple(self.get_value(var) for var in variable)
elif isinstance(variable, dict):
return {name: self.get_value(var) for name, var in variable.items()}
elif isinstance(variable, set):
return {self.get_value(var) for var in variable}
else:
return self.Value(variable)
@property
def solutions(self):
return self.__solutions.copy() # すべての解を辞書のリストで公開
以下かいつまんで説明します。
def __init__(self, *variable):
super().__init__()
self.__variable = variable[0] if len(variable) == 1 else tuple(variable)
まず決定変数を可変長引数（*variable）にして、タプルのまま受け取ります。こうすることで、複数の決定変数を渡されたときには、解をタプルで保持する仕様にしました。
引数が1個だけだったときには解をタプルにする必要がないので、self.__variableにも1個目の引数だけを格納しています。
def get_value(self, variable): # 同じ構造で値を返す
if isinstance(variable, list):
return [self.get_value(var) for var in variable]
elif isinstance(variable, tuple):
return tuple(self.get_value(var) for var in variable)
elif isinstance(variable, dict):
return {name: self.get_value(var) for name, var in variable.items()}
elif isinstance(variable, set):
return {self.get_value(var) for var in variable}
else:
return self.Value(variable)
渡された決定変数と同じ構造で値を返す関数がself.get_value()です。リスト、タプル、辞書、セット、単一の決定変数のどれかを判定し、同じ構造で値を返します。再帰的に入れ子にも対応しています。
def on_solution_callback(self):
self.__solutions.append(self.get_value(self.__variable))
on_solution_callbackでは、解の値をself.get_value()で取得しリストに追加しています。
このクラスを別ファイルに保存し、呼び出し側を以下のように書き換えます。
from ortools.sat.python import cp_model
+ from cp_solution_collector import CpSolutionCollector
### 中略 ###
# ソルバーで解く
solver = cp_model.CpSolver()
- collector = SolutionCollector(numbers)
+ collector = CpSolutionCollector(numbers)
status = solver.SearchForAllSolutions(model, collector)
if status in {cp_model.FEASIBLE, cp_model.OPTIMAL}:
print('解けました')
print(collector.solutions)
else:
print('解けませんでした')
実行すると、先ほどと同じ結果が出ます。
解けました
[[1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 3, 4, 5, 6, 7, 8, 9, 10]]
決定変数の渡し方に応じて、柔軟に解の値を保持できます。
collector = CpSolutionCollector(numbers[0]) # [1, 2]
collector = CpSolutionCollector(numbers[0], numbers[1]) # [(1, 2), (2, 3)]
collector = CpSolutionCollector({numbers[0], numbers[8]}) # [{1, 9}, {2, 10}]
collector = CpSolutionCollector({'first': numbers[0], 'last':numbers[8]})
# [{'first': 1, 'last': 9}, {'first': 2, 'last': 10}]
問題が複雑になると決定変数の数も多くなるので、名前で値を取得できる辞書で渡す方法が有効です。
次回は
連載の目標
- CPでパズル（ナンプレ、お絵描きロジック）を解いてみる
- ビジネス等へのCPの応用を検討できるようになる
ここまでCPの概念をお伝えするために目的のないサンプルを取り扱ってきました。
次からいよいよパズルを解いてみますが、お絵描きロジックでは考えることが一気に増えてしまいます。
ナンプレ（数独）は、数字を並べるだけで、絵が出来上がる訳でもないので、個人的にはあまり楽しいと思えない苦手なパズルですが、とてもCPで書きやすいルールなので、次回はナンプレを解いてみます。