概要
「サングラス」、というペンシルパズル(＝紙上で鉛筆と消しゴムを使って解くパズル)があります。
この前これの布教ツイートを見かけ、
#ふーのパズル#デレマスパズル部
— ふーなんとかさん(デレマスパズル部 7638パズル課) (@fuwa_lica_chan) October 10, 2020
サングラス(9*10)
10月10日はメガネの日、じゃなかった…
そしてメガネということで比奈(17)&春菜(867)で作ろうとしたら、なぜか日菜子(175)&成宮(7638)に…
ルールは画像1枚目をどうぞ。
想定難易度:3.6/5.0(強めのたいへん)
webで解く→ https://t.co/DQLmPTf7Bq pic.twitter.com/z3sGGMqawU
またネット上で解けるサイトも見つけたので、しばらく自力で遊んでいました。
こんなシンプルな盤面ですら、解答図が想像できないパズル、「サングラス」https://t.co/Dz4algVHKl pic.twitter.com/mWRz9YJo7l
— YSR@LUMIX S5ポチった！！！ (@YSRKEN) October 10, 2020
サングラス
— YSR@LUMIX S5ポチった！！！ (@YSRKEN) October 11, 2020
作： ふーなんとかさん さん
難易度：★4 (アゼン)https://t.co/6WFbARfFO5
さっき解いたので、ペンシルパズル「サングラス」完全に理解した pic.twitter.com/uaIIv9kUgq
ただ、なんとなく**これ自動で解けないかな？**と思ったので、ソルバーをPythonで作成することにしました。
なんでコンパイル言語じゃないかって？ C++で書くの辛いんじゃい！
作成したソルバー(Python製)：
基本方針
ソルバーの書き方は色々ありますが、今回は次のようにして解きました。
- 既存の手筋を使い、解けるところまで解く(これをfunc1とする)
- 中身が不定な1マスについて、「塗りつぶす」と仮定した状態でfunc1を走らせ、途中で矛盾が見つかった場合は「空白にする」
- 逆も同様で、「空白にする」と矛盾するなら「塗りつぶす」しかない(これをfunc2とする)
- 中身が不定な1マスについて、「塗りつぶす」と仮定した状態でfunc2を走らせ、途中で矛盾が見つかった場合は「空白にする」
- 逆も同様で、「空白にする」と矛盾するなら「塗りつぶす」しかない(これをfunc3とする)
func1は「手筋を使う方法」、func2は「1マスを仮定した背理法」、func3は「2マスを仮定した背理法」といったところでしょうか。
当初は「いきなり背理法を使い、矛盾が生じれば戻す」といった予定でしたが、計算コストが掛かりすぎるのでセーブした格好。
簡単な問題ならfunc1だけで解けるのですが、そうでない問題もままあります。
とりあえず、既存問題の「難易度：アゼン」までならfunc3までで十分かと。
使用した手筋
ブリッジの両端は塗りつぶす、その中間は空白にする
これはルールにも書いてあるのですぐ分かると思います。
レンズ同士が接触しないように空白を設置
以下、あるブリッジの両端から生えているレンズを「ブリッジのレンズ」、そうではない(まだどのブリッジから生えているか不定な)レンズを「孤立したレンズ」と呼びます。
ブリッジの両端、または異なるブリッジに属するレンズは、ルール上くっついてはいけません。
つまり、「あるマスが塗りつぶされると2つの(孤立していない、異なった)レンズがくっついてしまう」場合、「そのマス」を空白にする必要があります。
そのため、ブリッジのレンズそれぞれについて、その周囲1マス(斜め方向に隣接するものは含まない)に対し、「そこが塗りつぶされると他のレンズとくっついてしまわないか」を調べることで、空白マスに決定できます。
各ブリッジの両端のレンズにおける、塗りつぶし状態・上下左右の空白状態を同期
ルール上、ブリッジの両端のレンズは線対称になりますので、片方で塗りつぶされているマスは、もう一方でも必ず塗りつぶされます。
また、ブリッジのレンズの周囲1マス(上下左右方向のみ)に空白マスがあった場合、その状態も必ずコピーされます。
そうでないと、一方のレンズでそこが塗られた際、もう一方のレンズでも塗る必要があって矛盾してしまいます。
これを実装するためには、「ブリッジを基準にレンズを線対称に反転させたものを用意する」処理が必要ですが、これが非常に難しい。
現状提供されている盤面では、ブリッジの両端のマスの位置関係が「上下方向」「左右方向」「45度の斜め方向(2種)」だけなので、まだ場合分けで解決できますが、それ以外のシチュエーションで実装するのは無理ゲーじゃないのこれ……？
※例えば、ペンシルパズル「天体ショー」では、その名の通り点対称の概念が重要となる。だが、点対称の計算は線対称の計算より楽なので、ソルバー開発も比較的簡単と推測される
ヒント数字に従い、ちょうど塗りつぶせるなら塗り潰す
これもすぐ分かると思います。「余ってたら塗りつぶす」ケースと、「余ってたら空白にする」ケースの2種類があるので注意。
どのブリッジからも塗りつぶせない位置のマスは空白マス
一番説明しずらい手筋ですが、同時に最も重要な手筋です。例えば次のような盤面を考えます。
ここで赤色のマス(1列目・4行目)について考えると、いずれの「ブリッジのレンズ」も、このマスを取って「ブリッジのレンズ」の一部にできないだろうなー……というのは少し想像すれば分かるかと思います。
塗りつぶしを増やして強引に取っても、「ブリッジのレンズの両端は線対称で、他の(孤立していない)レンズとくっつけない」ルールに反してしまうからです。
その上、ルールから、どの「ブリッジのレンズ」にもくっつくことができない「孤立したレンズ」は盤面に残せませんので、この赤色のマスは必ず空白マスなのです。
このような推論を行うと、他のマスもどんどん空白マスだと確定できます。先ほどの状態から、ここまで盤面を埋めることができました。
さて問題は「どうやって赤色マスなどの『どのブリッジからも塗りつぶせない位置のマス』を決めるのか」です。
思案した結果、次のような作戦を思いつきました。
1. それぞれの「ブリッジのレンズ」について、最大限伸ばせる範囲を決める
例えば左上のブリッジにおける、左側の「ブリッジのレンズ」の最大範囲はこんな感じ(橙色で塗ってます)。
また、左上のブリッジにおける、右側の「ブリッジのレンズ」の最大範囲はこんな感じ。
どちらも、「他のレンズとぶつからない」「空白マスの設定は尊重する」「孤立したレンズは飲み込んでOK」という条件下で塗っています。
2. 各ブリッジの両端のレンズについては、「線対称である」条件から、実際に塗れる領域が狭まる
手筋の段では「どちらかでも塗ってたら塗れる」スタンスでしたが、それは確定事項だからであって、今回の場合は「どちらでも塗ってないと塗れない」になります。それぞれ、ここまで塗れる範囲が狭まりました。
3. そもそも、各ブリッジについては、「線対称の軸部分のマス」は塗れない
ブリッジ両端のレンズが線対称になる＆くっつけないルール上、その線対称の軸におけるマスは塗れません。
ただ、「線対称の軸」の定義が地味に分かりづらいので、以下に例を示します。
このルールにより、前述のブリッジ両端における、「最大限伸ばせる範囲」はこんな感じになります。
4. 全ての「ブリッジのレンズ」における「最大限伸ばせる範囲」をマージしたものを求め、そこから「どのブリッジからも塗りつぶせないマス」を逆算する
マージしたものがこれで、
そこから逆算したものはこれ。
背理法の「矛盾」判定について
現状の実装では、次の2つだけ実装しています。
- ヒント数字の条件をどうしても満たせない場合は矛盾
- ある列/行について、「塗りつぶした個数」＋「未定な個数」＜「ヒント数字」なら矛盾
- ある列/行について、「塗りつぶした個数」＞「ヒント数字」なら矛盾
- どのブリッジにも属せない「孤立したレンズ」が存在する場合は矛盾
- 言い換えると、盤面内のレンズを全て検索し、その中で「孤立したレンズである」「周囲(上下左右)が全て空白マスである」ものを探す