CPでパズルを解く - 正解がいくつもある問題


# はじめに

この連載は、主に制約プログラミング（以下CP）の未経験者・入門者の方を対象に、親しみのあるパズルを解くプログラムを例に、CPの考え方をお伝えしようとするものです。

:::note info
この記事の前提
* PythonとOR-Toolsの基礎知識と動作環境
* ひとつの解を出力する制約プログラムの書き方と考え方の理解

本連載の第1回「はじめての制約プログラミング」読了相当以上の方向けの内容です
:::

<details><summary>連載目次</summary>

連載は以下の記事に分かれています。既にCPになじみのある方は適宜読み飛ばしてください。
<dl>
<dt><a href="c9f63d6d44dc32c2086a">はじめての制約プログラミング</a></dt>
<dd>動作環境を構築し、簡単なプログラムでCPの考え方を解説します</dd>
<dt><a href="e71406961bfd95069e76">正解がいくつもある問題</a></dt>
<dd>コールバックを実装してすべての解を出力する方法を解説します</dd>
<dt><a href="a44c58f608adcbe84596">ナンプレ（数独）</a></dt>
<dd>おそらく最もCPが適用しやすいパズル「ナンプレ」を解いてみます</dd>
<dt><a href="7c7664ebd2c2109403fc">お絵描きロジック（最終回）</a></dt>
<dd>お絵描きロジックをCPを使って解いてみます</dd>
</dl>
</details>

ご意見・ご感想、また内容に誤り等を発見された場合には是非お知らせください。


# 正解がいくつもある問題

制約充足問題では、すべての制約を満たす解が複数あることが珍しくありません。

例えば前回取り上げた「整数が順に1ずつ増えていくリストを作る」問題では、整数の範囲を1～10のまま、リストの要素数を9個にすると、下のふたつのリストはどちらもすべての制約を満たします。

```python:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[2, 3, 4, 5, 6, 7, 8, 9, 10]
```


# コールバック

OR-ToolsのCPソルバーで複数の解を処理するには、ソルバーからコールバックされるクラスを用意します。

:::note warn
Google for Developersのドキュメントでは、コールバックを受け取るクラスを「ソリューションプリンタ」と呼んでいますが、これはサンプルのコールバックが解を表示しているからです。
:::

ソルバーの身になって考えれば、解をひとつ見つける度に処理を呼び元にリターンすると、次の解を探すには途中になっている探索を復旧しなくてはならず大変です。

解を見つけたらコールバックを呼び出す仕組みは、コールバックから処理が返ればそのまま探索の続きができるので合理的です。


## すべての解を表示する

まずはGoogle for Developersと同じようにソリューションプリンタを実装してみましょう。

```python:one_to_nine_printer.py
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('解けませんでした')
```

実行してみましょう。

```python:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[2, 3, 4, 5, 6, 7, 8, 9, 10]
解けました
```


### ソリューションプリンタ

ソルバーからコールバックを受け取るには、```cp_model.CpSolverSolutionCallback```を継承したクラスを用意します。

```python:
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```でその値を表示しています。
このプログラムでは、受け取るのが決定変数のリストなので、値もリスト化して表示しています。

:::note warn
Google for Developerでは、```__init__```の1行目は```cp_model.CpSolverSolutionCallback.__init__(self)```と書かれていますが、多重継承した場合に違いがあるため、筆者は```super().__init__()```と書くようにしています。
:::


### ソルバーの呼び出し

すべての解を求めるには、ソルバーにコールバックを受け取るオブジェクトを渡します。

```python:
# ソルバーで解く
solver = cp_model.CpSolver()
printer = SolutionPrinter(numbers)
status = solver.SearchForAllSolutions(model, printer)
```

最後の1行は以下のように書くこともできます。

```python:
solver.parameters.enumerate_all_solutions = True
status = solver.Solve(model, printer)
```


## すべての解を保持する

連載の後半で扱うお絵描きロジックでは、複数の解を保持して再利用する場面があります。ビジネス等にCPを応用することを考えても、解を再利用したくなるケースは多いと思います。

そこでここでは、コールバックを受け取るクラスで解を保持するように書き換えてみます。


### ソリューションコレクタ

```python:
"""
ソリューションコレクタ
"""
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```プロパティで解のリストを外部に公開して、ソルバーの呼び出し元がすべての解を取得できるようにしています。


### ソルバーの呼び出しと解の取得

呼び出し側は以下のように変更しました。

```python:
# ソルバーで解く
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('解けませんでした')
```

実行すると以下のように表示されます。

```python:
解けました
[[1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 3, 4, 5, 6, 7, 8, 9, 10]]
```


## 汎用ソリューションコレクタ

:::note warn
本節は専らpythonのプログラムの再利用の話になります。CPの学習に必要な内容ではありませんので、区別してお読みいただければ幸いです。
:::

先述の通り、この連載の後半でもソリューションコレクタを使います。
CPを応用する多くの場合に必要になるはずですが、その都度ソリューションコレクタを書くのは面倒です。

CPでは解くべき問題が変われば、決定変数の数や型、構造が変わります。
ソリューションコレクタには解を保持すべき決定変数を渡さなくてはならないので、渡された決定変数と同じ構造で解を保持するソリューションコレクタを書いてみました。

```python:cp_solution_collector.py
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()		# すべての解を公開
```

以下かいつまんで説明します。

```python:
	def __init__(self, *variable):
		super().__init__()
		self.__variable = variable[0] if len(variable) == 1 else tuple(variable)
```

まず決定変数を可変長引数（```*variable```）にしてタプルのまま受け取ります。こうすることで、複数の決定変数を渡されたときにその値をタプルで保持するようにしました。
引数が1個だけのときには解をタプルにする必要がないので、```self.__variable```にも1個目の引数だけを格納しています。

```python:
	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()```です。リスト、タプル、辞書、セット、単一の決定変数のどれかを判定し、同じ構造で値を返します。再帰的に入れ子にも対応しています。

```python:
	def on_solution_callback(self):
		self.__solutions.append(self.get_value(self.__variable))
```

```on_solution_callback```では、解の値を```self.get_value()```で取得しリストに追加しています。

このクラスを別ファイルに保存し、呼び出し側を以下のように書き換えます。

```diff_python:one_to_nine.py
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('解けませんでした')
```

実行すると、先ほどと同じ結果が出ます。

```python:
解けました
[[1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 3, 4, 5, 6, 7, 8, 9, 10]]
```

別な問題を解くことを想定して、整数のリストの合計を求める決定変数を追加し、可変長引数に渡してみます。

```diff_python:
# 決定変数
numbers = [model.NewIntVar(1, 10, f"numbers_{i}") for i in range(9)]
+ total = model.NewIntVar(0, 55, "total")

# 制約
for i in range(8):
	model.Add(numbers[i + 1] == numbers[i] + 1)
+ model.Add(total == sum(numbers))

# ソルバーで解く
solver = cp_model.CpSolver()
- collector = CpSolutionCollector(numbers)
+ collector = CpSolutionCollector(numbers, total)
status = solver.SearchForAllSolutions(model, collector)

if status in {cp_model.FEASIBLE, cp_model.OPTIMAL}:
	print('解けました')
    print(collector.solutions)
else:
	print('解けませんでした')
```

この場合、それぞれの解はタプルとして保持されます。

```python:
解けました
[([1, 2, 3, 4, 5, 6, 7, 8, 9], 45), ([2, 3, 4, 5, 6, 7, 8, 9, 10], 54)]
```

問題が複雑になると決定変数の数も多くなるので、名前でアクセスできるよう辞書で渡すのが便利かと思います。

```diff_python:
# ソルバーで解く
solver = cp_model.CpSolver()
- collector = CpSolutionCollector(numbers, total)
+ collector = CpSolutionCollector({'numbers': numbers, 'total': total})
status = solver.SearchForAllSolutions(model, collector)

if status in {cp_model.FEASIBLE, cp_model.OPTIMAL}:
	print('解けました')
-   print(collector.solutions)
+ 	solutions = collector.solutions
+ 	for i in range(len(solutions)):
+ 		print(f"解{i}", solutions[i]['numbers'], 'の合計は', solutions[i]['total'])
else:
	print('解けませんでした')
```

```python:
解けました
解0 [1, 2, 3, 4, 5, 6, 7, 8, 9] の合計は 45
解1 [2, 3, 4, 5, 6, 7, 8, 9, 10] の合計は 54
```

# 次回は

:::note info
連載の目標
* CPでパズル（ナンプレ、お絵描きロジック）を解いてみる
* ビジネス等へのCPの応用を検討できるようになる
:::

ここまでCPの概念をお伝えするために目的のないサンプルを取り扱ってきました。

次からいよいよパズルを解いてみますが、お絵描きロジックでは考えることが一気に増えてしまいます。

ナンプレ（数独）は、数字を並べるだけで、絵が出来上がる訳でもないので、個人的にはあまり楽しいと思えない苦手なパズルですが、とてもCPで書きやすいルールなので、次回はナンプレを解いてみます。