はじめに
この連載は、主に制約プログラミング（以下CP）の未経験者・入門者の方を対象に、親しみのあるパズルを解くプログラムを例に、CPの考え方をお伝えしようとするものです。
この記事の前提
- PythonとOR-Toolsの基礎知識と動作環境
- 複数の解を取得する制約プログラムの書き方と考え方の理解
本連載の第2回「正解がいくつもある問題を解く」読了相当以上の方向けの内容です
連載目次
連載は以下の記事に分かれています。既にCPになじみのある方は適宜読み飛ばしてください。
- はじめての制約プログラミング
- 動作環境を構築し、簡単なプログラムでCPの考え方を解説します
- 正解がいくつもある問題
- コールバックを実装してすべての解を出力する方法を解説します
- ナンプレ（数独）
- おそらく最もCPが適用しやすいパズル「ナンプレ」を解いてみます
- お絵描きロジック（最終回）
- お絵描きロジックをCPを使って解いてみます
ご意見・ご感想、また内容に誤り等を発見された場合には是非お知らせください。
お絵描きロジックとは
英語では Nonogram、日本ではお絵描きロジックやイラストロジックと呼ばれる、数字のヒントからドット絵を完成させるパズルです。任天堂がピクロスという名前でゲーム化して有名になりました。
ヒントは行（ヨコ）のヒントと列（タテ）のヒントがあり、どちらも連続する黒マスの数を表しています。ヒントに数字が複数ある行や列では、連続する黒マスのブロックが複数あり、1つ以上の白マスで分かれています。
決まりはこれだけなので、ルールだけ見ると第3回で扱ったナンプレよりもシンプルですが、これを解くプログラムは少し複雑になります。
パズル系の出版物ではよく、完成したドット絵を見てお題を答える形式で出題されますが、解像度が低いのでお題にヒントがついているケースが多いようです。
本連載ではドット絵が完成した時点でお絵描きロジックが解けたものとします。
お絵描きロジックを解くプログラム
早速CPで解いていきます。モデルの初期化はいつも通りです。
決定変数
お絵描きロジックは、マス目を塗るか塗らないかの二択なので、Bool型の二次元のリストを決定変数にします。
ドット絵のサイズは幅がlen(col_hints)、高さがlen(row_hints)なので、決定変数よりも先にヒントを用意しています。
# ヒント
row_hints = [[1], [5], [1], [3], [1, 1]]
col_hints = [[1, 1], [1, 1], [4], [1, 1], [1, 1]]
# 決定変数
grid = [[model.NewBoolVar(f'cell_{x}_{y}') for x in range(len(col_hints))] for y in range(len(row_hints))]
制約
お絵描きロジックにはナンプレのようなルールはないので、ヒントからそれぞれの行や列に制約を追加していきます。
ここである行や列（以下「ライン」と呼びます）のヒントと長さ（マスの数）が決まると、あり得る塗りつぶしのパターンは有限個に定まります。
例えばヒントが[2, 1]、ラインの長さが5の場合には、そのラインは以下の3パターンのうちいずれかです。
OR-ToolsのCPモデルには、このような「許容されるパターン」を制約として追加する CpModel.AddAllowedAssignments(self, variables, tuples_list) メソッドが用意されているので、
# 制約
for row, hint in zip(grid, row_hints): # 行
model.AddAllowedAssignments(row, nono_allowed(hint, len(row)))
for column, hint in zip(zip(*grid), col_hints): # 列
model.AddAllowedAssignments(column, nono_allowed(hint, len(column)))
と書くことができます。ここで nono_allowed(hint, length) は許容されるBool値のタプルのリストを返す関数（後述）で、上図の場合の nono_allowed([2, 1], 5) は [(True, True, False, True, False), (True, True, False, False, True), (False, True, True, False, True)] を返すことを期待しています。
zip() を使って行と対応するヒント、列と対応するヒントを取り出しています。
列の取り出し部の zip(*grid) については第3回の記事にノートがあります。
ソルバーで解く
ひとまず関数（nono_allowed()）は置いておいて、ソルバーで解いて解を表示する部分を書いておきます。
以下、関数を除くプログラムです。（第2回で作ったcp_solution_collector.pyをimportしています）
from ortools.sat.python import cp_model
from cp_solution_collector import CpSolutionCollector
"""
メイン
"""
# モデルの初期化
model = cp_model.CpModel()
# ヒント
row_hints = [[1], [5], [1], [3], [1, 1]]
col_hints = [[1, 1], [1, 1], [4], [1, 1], [1, 1]]
# 決定変数
grid = [[model.NewBoolVar(f'cell_{x}_{y}') for x in range(len(col_hints))] for y in range(len(row_hints))]
# 制約
for row, hint in zip(grid, row_hints): # 行
model.AddAllowedAssignments(row, nono_allowed(hint, len(row)) )
for column, hint in zip(zip(*grid), col_hints): # 列
model.AddAllowedAssignments(column, nono_allowed(hint, len(column)))
# ソルバーで解く
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(''.join('■' if cell else '□' for cell in row))
else:
print('解けませんでした')
まだ関数を書いていないので実行するとエラーになります。
許容されるBool値のタプルのリストを作る
まず先ほどの図を再掲します。
これをpythonで次のコードと結果になるような関数 nono_allowed(hint, length) を作れば、お絵描きロジックが解けるはずです。
allowed = nono_allowed([2, 1], 5)
print(allowed)
# [(True, True, False, True, False), (True, True, False, False, True), (False, True, True, False, True)]
nono_allowed(hint, length) 関数は手続き型でも書けそうですが、再帰呼び出しを使うなどの工夫が必要で、アルゴリズムを考えるのもちょっと面倒なので、ここもCPで書いてしまいます。
決定変数
塗りつぶすドットの連続（ブロック）の数はヒントのリストの長さと一致します。
各ブロックのドットの数はヒントの各要素（整数）で与えられているので、あとは各ブロックの開始位置さえ決まればパターンが作れそうです。
# 決定変数
start = [model.NewIntVar(0, length - 1, f"start_{i}") for i in range(len(hint))]
各ブロックの開始位置はゼロ以上length未満の整数です。
制約
複数のブロックの間には1個以上の白マスがあるので、start[n + 1] は start[n] + hint[n] より大きいはずです。
# 制約
for i in range(len(hint) - 1):
model.Add(start[i] + hint[i] < start[i + 1])
これで各ブロックの間隔には制約をかけたので、最後のブロックがラインをはみ出さないように上限にも制約をかけます。
model.Add(start[-1] + hint[-1] <= length)
先の図の場合、この問題の解のリストは [[0, 3], [0, 4], [1, 4]] になります。
開始位置とヒントからBool列を作りリスト化する
関数が期待されている戻り値はBoolのタプルのリストなので、解をBool列（Boolのタプル）に変換して戻り値のリストに追加する処理が必要です。
allowed = []
for solution in solutions:
line = []
for s, l in zip(solution, hint):
line += [False] * (s - len(line)) + [True] * l
if (len(line) < length):
line += [False] * (length - len(line))
allowed.append(tuple(line))
ひとつの解には複数のブロックがあるので、空のリスト line を用意し、False を start[n] - len(line)個、True を hint[n]個追加する操作をブロックの数だけ繰り返します。
最後に length - len(line) 個のFalseを付け足せば、ひとつの解をBoolのリストに変換できるので、tuple()でタプルに変換して戻り値 allowed に追加しています。
特殊なケースの考慮
お絵描きロジックのヒントの特殊形として、[] または [0] があります。
ラインに塗るべきドットがひとつもないことを意味していますが、問題によって 0 と書いてあったり、ヒントが空だったりするようです。
このままだと、ヒントが空だとlist index out of rangeエラーになります。0 だと 0 <= start and start < length を満たすstartすべてが制約を満たしてしまうため、Falseで埋まったタプルをlength個返してしまいます。
いずれも False で埋まった長さ length のタプルひとつだけを含むリストを返せばよいので、関数の先頭で判断することにしました。
# ヒントが空（[] or [0]）だったら
if (sum(hint) == 0):
return [tuple([False] * length)] # すべてFalseを返す
また今回この関数もCPで書いたので、解けないケースも考慮する必要があります。
具体的には、length < sum(hint) + len(hint) - 1 の場合、ヒントを満たすドットの並びがラインに収まりきらないので解がみつかりません。
解けないのはこのケースだけかも知れませんが、今回はソルバーのステータスを判断してエラーを発生させ、メイン側で例外をトラップします。（コードは次節）
完成したプログラム
関数をimportとメインの間に差し込み、メインに前節の最後に説明した例外処理を加えて、完成したプログラムです。
from ortools.sat.python import cp_model
from cp_solution_collector import CpSolutionCollector
"""
nono_allowed
"""
def nono_allowed(hint, length):
# ヒントが空（[] or [0]）だったら
if (sum(hint) == 0):
return [tuple([False] * length)] # すべてFalseを返す
# モデルの初期化
model = cp_model.CpModel()
# 決定変数
start = [model.NewIntVar(0, length - 1, f"start_{i}") for i in range(len(hint))]
# 制約
for i in range(len(hint) - 1):
model.Add(start[i] + hint[i] < start[i + 1])
model.Add(start[-1] + hint[-1] <= length)
# ソルバーで解く
solver = cp_model.CpSolver()
solution_collector = CpSolutionCollector(start)
status = solver.SearchForAllSolutions(model, solution_collector)
if status in {cp_model.FEASIBLE, cp_model.OPTIMAL}:
# 解けました
allowed = []
solutions = solution_collector.solutions
for solution in solutions:
line = []
for s, l in zip(solution, hint):
line += [False] * (s - len(line)) + [True] * l
if (len(line) < length):
line += [False] * (length - len(line))
allowed.append(tuple(line))
return allowed
else:
# 解けませんでした
raise ValueError(f"(hint, length)=({hint}, {length})：パターンが作れませんでした")
"""
メイン
"""
# モデルの初期化
model = cp_model.CpModel()
# ヒント
row_hints = [[1], [5], [1], [3], [1, 1]]
col_hints = [[1, 1], [1, 1], [4], [1, 1], [1, 1]]
# 決定変数
grid = [[model.NewBoolVar(f'cell_{x}_{y}') for x in range(len(col_hints))] for y in range(len(row_hints))]
# 制約
try:
for row, hint in zip(grid, row_hints): # 行
model.AddAllowedAssignments(row, nono_allowed(hint, len(row)) )
for column, hint in zip(zip(*grid), col_hints): # 列
model.AddAllowedAssignments(column, nono_allowed(hint, len(column)))
except ValueError as e:
print(e)
exit(1)
# ソルバーで解く
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(''.join('■' if cell else '□' for cell in row))
else:
print('解けませんでした')
実行すると、お絵描きロジックが解けました。
解けました
解 1
□□■□□
■■■■■
□□■□□
□■■■□
■□□□■
やはり解像度が低くて、お題のヒントなしでは何にでも見えてしまいますね。
ちなみに、主にお盆の時期に送り火として行われる行事を意識して問題を作ったのですが、解が一意にならなかったので二股の間をドットでつないでしまい、もっとわからなくなりました（汗）。
さいごに
連載の目標
- CPでパズル（ナンプレ、お絵描きロジック）を解いてみる
- ビジネス等へのCPの応用を検討できるようになる
いかがでしたでしょうか。
記事はパズルという、解けてもただ楽しいだけのテーマで書きましたが、ITの仕事をされている方であれば、ビジネスにも応用できることがなんとなくご理解いただけたのではないかと思います。
この連載では、CPの概要しかお伝えできていませんが、制約プログラミングに興味を持たれる方がおひとりでも増えれば幸いです。