夏休みなので Python でロジックパズルを解きました。なお、Python には退屈なことをやらせるべきであって、パズルを解かせるのは台無しだと思います。
ロジックパズルとは
出典が不十分らしいですが以下の記事のような問題をロジックパズルとよぶことにします。
ロジックパズル - Wikipedia
例えば図は私が作ったロジックパズルです。
上図のパズルの正解は以下になります。
このように、ロジックパズルとは、それぞれ要素に重複のないような長さ n の列が m 本与えられ ( 名前列, 学年列, 食べ物列, スポーツ列 )、「あちらの列があの値をとるときこちらの列の値はこうなる」といったヒントたちが与えられ、それらをもとに 1 列目の各値に対応する 2 列目以降の値を特定する問題のことをいいます (たぶん)。ただし、1 列目の異なる値に 2 列目以降の同じ値が対応することはありません (Ex. アリスもボブもお寿司が好きということはありません) (つまり、1 列目の値から 2 列目以降の各列の値への対応は単射です)。
いいかえると、ロジックパズルは 2 列目以降の n-順列 を特定する問題ともいえます。
なお、上の例題のような基本的なロジックパズルでは m 本の列の長さが全て n ですが、応用問題では 2 列目以降の列の長さが n より長いこともあります。1
ロジックパズルを解く方法 (紙と鉛筆で)
ロジックパズルを解く方法の一案としては、正解候補を一つ一つヒントたちと整合的か検証する総当たり法 (ブルートフォース) があると思います。しかし、基本的な n 行 m 列ロジックパズルは正解候補が nPn^(m-1) 通りあります。上の例題 (5 行 4 列) では 120 * 120 * 120 = 1728000 通りあります。紙と鉛筆でこれを一つ一つ検証するのは大変そうです。
そこで、紙と鉛筆で解く場合は通常、よく問題に備え付けられている、階段をひっくり返したような形のマス目を使います。この問題では 25 マスのブロックが 6 ブロックあります。
このマス目の使い方については色々解説があると思いますが、以下のように使用すれば問題が解けると思います。
- まず、表のマス目にヒントからただちにわかるマルやバツを一通り書き入れます。同じ名前、同じ学年、同じ食べ物好き、同じスポーツ好きの人は 2 人といないので、どこかにマルが入ったときは同一ブロック内のマルの上下左右すべてのマスにバツが入ります。
- 次に、マルに基づいて「同期」をします。例えば、下図の赤いマルに着目すると、
- 3 年生 → アリス の同期：アリスは 3 年生であると判明したので、3 年生の情報をアリスに同期します。つまり、3年生はバスケ好きではないので、アリスもバスケ好きではありません (そして、これによってアリスがサッカー好きであることが判明します)。
- アリス → 3 年生 の同期： 逆に 3 年生の正体はアリスであることが判明したので、アリスの情報を 3 年生に同期します。つまり、アリスはテニス、マラソン、水泳、寿司、ステーキが好きではないので、3 年生もそれらが好きではありません。
- 一通り同期すると新たな情報が判明してくるのでまた同期することを繰り返し、最上段ブロックたちのマス目が埋まれば OK です。各名前行のマルの位置が正解を示しています。
なお、この例題では必要ないと思いますが、列数 m が増えてくると、ただちに埋められるマスの同期だけではマス目が埋まらず、背理法をつかう必要が出てくると思います (もしここがマルであると、ここがマルになり、ここがマルになるが、そこには既にバツがあるので矛盾、といったように)。
ではこのマス目は何なのかというと、正解を m 次元空間内のセルに配置した n 個のボールにエンコードしたもの、を各平面に投影した図といえると思います。その観点で上図をみると、学年座標が 3 年生の位置にあるボールはスポーツ座標がバスケではないことがわかりますが、このボールは名前座標がアリスの位置にあるボールに他ならないので、名前座標がアリスの位置にあるボールもまたスポーツ座標がバスケではありません (3 年生 → アリス の同期)。
ロジックパズルを解く方法 (Pythonで)
結論からいうと以下のように LogicPuzzle クラスを実装しました。インポートして使用できます (このスクリプトを直接サンプル実行することもできます)。
CookieBox26/logic_puzzle.py
クラスの使い方
問題のデータとヒントを以下のように与えて実行します。
「デイヴはキャロルの 3 学年下」というヒントは、「デイブの学年はオフセット 3 を足すとキャロルの学年に等しい」というように与えます。
from logic_puzzle import LogicPuzzle # クラスファイルを隣に置く場合
def main():
data = [
('名前', ('アリス', 'ボブ', 'キャロル', 'デイヴ', 'エレン')),
('学年', (1, 2, 3, 4, 5)),
('好きな食べ物', ('寿司', 'ハンバーガー', 'カレー', 'ラーメン', 'ステーキ')),
('好きなスポーツ', ('テニス', 'サッカー', 'バスケ', 'マラソン', '水泳')),
]
puzzle = LogicPuzzle(data)
hints = (
(('名前', 'アリス', '学年'), 3, '=='),
(('名前', 'アリス', '好きなスポーツ'), 'マラソン', '!='),
(('名前', 'ボブ', '好きなスポーツ'), 'テニス', '=='),
(('名前', 'ボブ', '好きな食べ物'), '寿司', '=='),
(('名前', 'エレン', '学年'), 2, '>='),
(('名前', 'デイヴ', '学年'), ('名前', 'キャロル', '学年'), '==', 3),
(('名前', 'エレン', '好きなスポーツ'), '水泳', '=='),
(('名前', 'デイヴ', '好きな食べ物'), 'ステーキ', '=='),
(('学年', 2, '好きなスポーツ'), 'バスケ', '=='),
(('好きな食べ物', 'ハンバーガー', '学年'), ('好きな食べ物', 'ラーメン', '学年'), '<'),
(('好きな食べ物', 'ラーメン', '学年'), ('好きな食べ物', 'カレー', '学年'), '<'),
)
puzzle.reflect(hints, sort=True)
if __name__ == '__main__':
main()
実行結果は以下のようになります。
問題を読み込みました。(理論パターン数: 1728000)
変数名の列 (並べ替え前): ('名前', '学年', '好きな食べ物', '好きなスポーツ')
変数名の列 (並べ替え後): ('名前', '学年', '好きなスポーツ', '好きな食べ物')
2 つ目の変数までの組合せ数 (絞込み前): 120
2 つ目の変数までの組合せ数 (絞込み後): 3
3 つ目の変数までの組合せ数 (絞込み前): 360
3 つ目の変数までの組合せ数 (絞込み後): 1
4 つ目の変数までの組合せ数 (絞込み前): 120
4 つ目の変数までの組合せ数 (絞込み後): 1
正答は以下です。
----- 0 -----
('アリス', 'ボブ', 'キャロル', 'デイヴ', 'エレン')
(3, 1, 5, 2, 4)
('ハンバーガー', '寿司', 'カレー', 'ステーキ', 'ラーメン')
('サッカー', 'テニス', 'マラソン', 'バスケ', '水泳')
--------------
実行結果の出力からやっていることが何となくわかると思いますが、2 列目まで、3 列目まで、……の組合せを構成すると同時に、随時ヒントを用いて組合せを絞り込んでいます。随時絞り込まずに一気に 4 列の組合せを構成して絞り込もうとすると、120 * 120 * 120 = 1728000 通りの組合せを検証する羽目になるからです。
列ソート機能
上の実行結果に以下のような出力がありますが、これは字のごとく列をソートしています。これは、なるべく早い段階で多くのヒントを消化するために、列順たちに優先度スコアを割り振って、最優先の列順を採用しているためです。2
変数名の列 (並べ替え前): ('名前', '学年', '好きな食べ物', '好きなスポーツ')
変数名の列 (並べ替え後): ('名前', '学年', '好きなスポーツ', '好きな食べ物')
一応この列ソートはキャンセルすることもできます。
def main():
# 略
puzzle.reflect(hints, sort=False)
列ソートしない場合は以下のように、4 つ目までの組合せを検証開始する時点で 360 パターンが残っており、ソートした場合の 120 パターンの 3 倍のパターン数が残っています。とはいえ、この例ではほとんど恩恵は感じられないと思います。
2 つ目の変数までの組合せ数 (絞込み前): 120
2 つ目の変数までの組合せ数 (絞込み後): 3
3 つ目の変数までの組合せ数 (絞込み前): 360
3 つ目の変数までの組合せ数 (絞込み後): 3
4 つ目の変数までの組合せ数 (絞込み前): 360
4 つ目の変数までの組合せ数 (絞込み後): 1
変数名の列 (並べ替え前): ('名前', '学年', '好きな食べ物', '好きなスポーツ')
変数名の列 (並べ替え後): ('名前', '学年', '好きなスポーツ', '好きな食べ物')
2 つ目の変数までの組合せ数 (絞込み前): 120
2 つ目の変数までの組合せ数 (絞込み後): 3
3 つ目の変数までの組合せ数 (絞込み前): 360
3 つ目の変数までの組合せ数 (絞込み後): 1
4 つ目の変数までの組合せ数 (絞込み前): 120
4 つ目の変数までの組合せ数 (絞込み後): 1
より列数が大きい問題だと恩恵を感じられることがあります。以下は市販本の問題を解いた結果ですが、ランダムソートでひどい場合のほうは途中で 69 万パターンとか 127 万パターンの検証が発生しています (なお、5 行 6 列パズルなので組合せ総数は 249 億になります)。
問題を読み込みました。(理論パターン数: 24883200000)
2 つ目の変数までの組合せ数 (絞込み前): 120
2 つ目の変数までの組合せ数 (絞込み後): 12
3 つ目の変数までの組合せ数 (絞込み前): 1440
3 つ目の変数までの組合せ数 (絞込み後): 72
4 つ目の変数までの組合せ数 (絞込み前): 8640
4 つ目の変数までの組合せ数 (絞込み後): 248
5 つ目の変数までの組合せ数 (絞込み前): 29760
5 つ目の変数までの組合せ数 (絞込み後): 192
6 つ目の変数までの組合せ数 (絞込み前): 23040
6 つ目の変数までの組合せ数 (絞込み後): 1
問題を読み込みました。(理論パターン数: 24883200000)
2 つ目の変数までの組合せ数 (絞込み前): 120
2 つ目の変数までの組合せ数 (絞込み後): 120
3 つ目の変数までの組合せ数 (絞込み前): 14400
3 つ目の変数までの組合せ数 (絞込み後): 5760
4 つ目の変数までの組合せ数 (絞込み前): 691200
4 つ目の変数までの組合せ数 (絞込み後): 10560
5 つ目の変数までの組合せ数 (絞込み前): 1267200
5 つ目の変数までの組合せ数 (絞込み後): 1248
6 つ目の変数までの組合せ数 (絞込み前): 149760
6 つ目の変数までの組合せ数 (絞込み後): 1
ヒントの冗長性チェック機能
人生でロジックパズルを作問することもあると思います。そのとき、ヒントの冗長性を排除したいとなると思います。LogicPuzzle クラスにはそのチェック機能も実装しています。
- Ex. 1 は例題のヒントをそのままチェックした場合です。
- Ex. 2 は例題のヒントに「アリスはカレーが好きではない」を加えてチェックした場合です。これは不要なヒントであることがわかります。
- 「そのヒントを取り除いたとしても他のヒントたちから正答がただ 1 つに定まる」というヒントを画面に出力します。複数出力された場合は、それらのうちどれか 1 つを取り除いてもよいという意味なので、すべて取り除かないでください。
- Ex. 3 は例題のヒントから「アリスはマラソンが好きではない」を取り除いてチェックした場合です。この場合は正解が定まらないことがわかります。
def main():
# 略
puzzle.check_redundancy(hints)
ヒントの冗長性を確認します。
これらのヒントに冗長なものはありません。
ヒントの冗長性を確認します。
2 番目のヒントは必要ありません。(('名前', 'アリス', '好きな食べ物'), 'カレー', '!=')
ヒントの冗長性を確認します。
これらのヒントでは正答が定まりません。(残りパターン数: 2)
----- 0 -----
('アリス', 'ボブ', 'キャロル', 'デイヴ', 'エレン')
(3, 1, 5, 2, 4)
('ハンバーガー', '寿司', 'カレー', 'ステーキ', 'ラーメン')
('サッカー', 'テニス', 'マラソン', 'バスケ', '水泳')
--------------
----- 1 -----
('アリス', 'ボブ', 'キャロル', 'デイヴ', 'エレン')
(3, 1, 5, 2, 4)
('ハンバーガー', '寿司', 'カレー', 'ステーキ', 'ラーメン')
('マラソン', 'テニス', 'サッカー', 'バスケ', '水泳')
--------------
その他TIPS
2 列目以降が 1 列目より長くても構いません。ただ、重複のない列にしてください。
data = [
('名前', ('アリス', 'ボブ', 'キャロル', 'デイヴ', 'エレン')),
('学年', (1, 2, 3, 4, 5, 6, 7, 8, 9)),
]
列がテストの点数であるときに、「アリスとボブはテストの順位が 1 つ違いであった」というヒントを与えることもできます。具体的に、点数の列はソートしておき、「アリスの点数のインデクスとボブの点数のインデクスは絶対差が 1 であった」というヒントを与えます。
「順位の差が2つ以上だった」「順位の差が2つ以内であった」というヒントも可能です。
data = [
('名前', ('アリス', 'ボブ', 'キャロル', 'デイヴ', 'エレン')),
('点数', (450, 400, 350, 300, 250)),
]
hints = (
(('名前', 'アリス', '点数', 'index'), ('名前', 'ボブ', '点数', 'index'), 'absdiff==', 1),
)
「アリスの好きな食べ物は麺類である」といった、「この範囲の中のどれか」系のヒントについては、「この範囲の外のどれでもない」という形で与えてください。
data = [
('名前', ('アリス', 'ボブ', 'キャロル', 'デイヴ', 'エレン')),
('好きな食べ物', ('ラーメン', 'パスタ', 'うどん', 'チャーハン', '牛丼')),
]
hints = (
(('名前', 'アリス', '好きな食べ物'), 'チャーハン', '!='),
(('名前', 'アリス', '好きな食べ物'), '牛丼', '!='),
)
TBD
- 2 列の値の計算結果に基づくヒントは、compare メソッドを修正する必要があります。
- Ex. 身長列と体重列があるときに、「ボブの BMI は 25 未満である」など。
- 3 列以上の値の計算結果に基づくヒントには対応していません。スクリプトを結構改修する必要があると思います。
-
例えば、例題では 5 人の学年が 1, 2, 3, 4, 5 年生のどれかであるとしていますが、6 年生もありえることにしてもよいです。その場合、マトリクスの「学年」の部分が空欄になっていて、回答者は何年生が存在するのかから解くことになります。なお、例題そのままで 6 年生を選択肢に含めると正解が 1 通りに特定できない ( 4 通りの可能性が残ってしまう ) ので、ヒントを追加する必要があります。 ↩
-
列順に対してその列順の優先度スコアを仮に、「2列目までだけで適用できるヒントの数 + 0.1 * 3列目までだけで適用できるヒントの数 + 0.01 * 4列目までだけで適用できるヒントの数 + ...」としています。ただし、ヒントの中でもイコールヒントは列の長さだけ、不等号ヒントは列の長さの半分だけの重みを乗じます (これらはノットイコールヒントより絞り込み力が高いと思われるからです)。ただし、特に冗長なヒントがあるとこの優先付けはかなり狂いますし、あくまでおおよその見積もりであって、最適な列順を選択できるわけではありません。よりよいスコア付けを教えてください。 ↩