ペンシルパズル「サングラス」用のソルバーを作ったので技術解説をば


概要

「サングラス」、というペンシルパズル(=紙上で鉛筆と消しゴムを使って解くパズル)があります。

この前これの布教ツイートを見かけ、

またネット上で解けるサイトも見つけたので、しばらく自力で遊んでいました。

ただ、なんとなくこれ自動で解けないかな?と思ったので、ソルバーを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つだけ実装しています。

  • ヒント数字の条件をどうしても満たせない場合は矛盾
    • ある列/行について、「塗りつぶした個数」+「未定な個数」<「ヒント数字」なら矛盾
    • ある列/行について、「塗りつぶした個数」>「ヒント数字」なら矛盾
  • どのブリッジにも属せない「孤立したレンズ」が存在する場合は矛盾
    • 言い換えると、盤面内のレンズを全て検索し、その中で「孤立したレンズである」「周囲(上下左右)が全て空白マスである」ものを探す