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

# 概要

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

- [サングラスについて考えてみよう（基本編）｜nyoroppyi｜note](https://note.com/nyoroppyi/n/n71344c45574b)

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

<blockquote class="twitter-tweet" data-partner="tweetdeck"><p lang="ja" dir="ltr"><a href="https://twitter.com/hashtag/%E3%81%B5%E3%83%BC%E3%81%AE%E3%83%91%E3%82%BA%E3%83%AB?src=hash&amp;ref_src=twsrc%5Etfw">#ふーのパズル</a><a href="https://twitter.com/hashtag/%E3%83%87%E3%83%AC%E3%83%9E%E3%82%B9%E3%83%91%E3%82%BA%E3%83%AB%E9%83%A8?src=hash&amp;ref_src=twsrc%5Etfw">#デレマスパズル部</a><br>サングラス(9*10)<br><br>10月10日はメガネの日、じゃなかった…<br>そしてメガネということで比奈(17)&amp;春菜(867)で作ろうとしたら、なぜか日菜子(175)&amp;成宮(7638)に…<br><br>ルールは画像1枚目をどうぞ。<br><br>想定難易度:3.6/5.0(強めのたいへん)<br>webで解く→ <a href="https://t.co/DQLmPTf7Bq">https://t.co/DQLmPTf7Bq</a> <a href="https://t.co/z3sGGMqawU">pic.twitter.com/z3sGGMqawU</a></p>&mdash; ふーなんとかさん(デレマスパズル部 7638パズル課) (@fuwa_lica_chan) <a href="https://twitter.com/fuwa_lica_chan/status/1314913582467883009?ref_src=twsrc%5Etfw">October 10, 2020</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

また[ネット上で解けるサイト](https://puzsq.jp/main/index.php?puzzle=128)も見つけたので、しばらく自力で遊んでいました。

<blockquote class="twitter-tweet" data-partner="tweetdeck"><p lang="ja" dir="ltr">こんなシンプルな盤面ですら、解答図が想像できないパズル、「サングラス」<a href="https://t.co/Dz4algVHKl">https://t.co/Dz4algVHKl</a> <a href="https://t.co/mWRz9YJo7l">pic.twitter.com/mWRz9YJo7l</a></p>&mdash; Y​S​R​@​L​U​M​I​X​ ​S​5​ポ​チ​っ​た​！​！​！ (@YSRKEN) <a href="https://twitter.com/YSRKEN/status/1314971391490322433?ref_src=twsrc%5Etfw">October 10, 2020</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet" data-partner="tweetdeck"><p lang="ja" dir="ltr">サングラス<br>作： ふーなんとかさん さん<br>難易度：★4 (アゼン)<a href="https://t.co/6WFbARfFO5">https://t.co/6WFbARfFO5</a><br><br>さっき解いたので、ペンシルパズル「サングラス」完全に理解した <a href="https://t.co/uaIIv9kUgq">pic.twitter.com/uaIIv9kUgq</a></p>&mdash; Y​S​R​@​L​U​M​I​X​ ​S​5​ポ​チ​っ​た​！​！​！ (@YSRKEN) <a href="https://twitter.com/YSRKEN/status/1315262586774937601?ref_src=twsrc%5Etfw">October 11, 2020</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

ただ、なんとなく**これ自動で解けないかな？**と思ったので、ソルバーをPythonで作成することにしました。
なんでコンパイル言語じゃないかって？　**C++で書くの辛いんじゃい！**

## 作成したソルバー(Python製)：
https://github.com/YSRKEN/puzzle_sunglass_solver

# 基本方針

ソルバーの書き方は色々ありますが、今回は次のようにして解きました。

- 既存の手筋を使い、解けるところまで解く(これをfunc1とする)
- 中身が不定な1マスについて、「塗りつぶす」と仮定した状態でfunc1を走らせ、途中で矛盾が見つかった場合は「空白にする」
  - 逆も同様で、「空白にする」と矛盾するなら「塗りつぶす」しかない(これをfunc2とする)
- 中身が不定な1マスについて、「塗りつぶす」と仮定した状態でfunc2を走らせ、途中で矛盾が見つかった場合は「空白にする」
  - 逆も同様で、「空白にする」と矛盾するなら「塗りつぶす」しかない(これをfunc3とする)

func1は「手筋を使う方法」、func2は「1マスを仮定した背理法」、func3は「2マスを仮定した背理法」といったところでしょうか。
当初は「いきなり背理法を使い、矛盾が生じれば戻す」といった予定でしたが、計算コストが掛かりすぎるのでセーブした格好。

簡単な問題ならfunc1だけで解けるのですが、そうでない問題もままあります。
とりあえず、既存問題の「難易度：アゼン」までならfunc3までで十分かと。

# 使用した手筋

## ブリッジの両端は塗りつぶす、その中間は空白にする

これはルールにも書いてあるのですぐ分かると思います。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/7e971634-2506-5168-58bd-5b1b4190f9e4.png)

## レンズ同士が接触しないように空白を設置

以下、あるブリッジの両端から生えているレンズを「ブリッジのレンズ」、そうではない(まだどのブリッジから生えているか不定な)レンズを「孤立したレンズ」と呼びます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/b06b6fad-671b-b174-81b7-1ed44c46b924.png)

ブリッジの両端、または異なるブリッジに属するレンズは、ルール上くっついてはいけません。
つまり、「あるマスが塗りつぶされると2つの(孤立していない、異なった)レンズがくっついてしまう」場合、**「そのマス」を空白にする必要があります**。

そのため、ブリッジのレンズそれぞれについて、その周囲1マス(斜め方向に隣接するものは含まない)に対し、「そこが塗りつぶされると他のレンズとくっついてしまわないか」を調べることで、空白マスに決定できます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/733ac6c4-5eac-a995-32d8-1e66dd0f8d09.png)

## 各ブリッジの両端のレンズにおける、塗りつぶし状態・上下左右の空白状態を同期

ルール上、ブリッジの両端のレンズは線対称になりますので、片方で塗りつぶされているマスは、もう一方でも必ず塗りつぶされます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/b57f1dde-cb71-9353-e5e7-289460cc47b6.png)

また、ブリッジのレンズの周囲1マス(上下左右方向のみ)に空白マスがあった場合、その状態も必ずコピーされます。
そうでないと、一方のレンズでそこが塗られた際、もう一方のレンズでも塗る必要があって矛盾してしまいます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/9d51ad3a-77fe-f750-8b6e-d3403f42180b.png)

これを実装するためには、「ブリッジを基準にレンズを線対称に反転させたものを用意する」処理が必要ですが、これが**非常に難しい**。
現状提供されている盤面では、ブリッジの両端のマスの位置関係が「上下方向」「左右方向」「45度の斜め方向(2種)」だけなので、まだ場合分けで解決できますが、それ以外のシチュエーションで実装するのは無理ゲーじゃないのこれ……？

※例えば、ペンシルパズル「天体ショー」では、その名の通り点対称の概念が重要となる。だが、**点対称の計算は線対称の計算より楽**なので、ソルバー開発も比較的簡単と推測される

## ヒント数字に従い、ちょうど塗りつぶせるなら塗り潰す

これもすぐ分かると思います。「余ってたら塗りつぶす」ケースと、「余ってたら空白にする」ケースの2種類があるので注意。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/2dbfc718-7141-2d95-be3a-227fbb3fb867.png)

## どのブリッジからも塗りつぶせない位置のマスは空白マス

一番説明しずらい手筋ですが、同時に**最も重要な手筋**です。例えば次のような盤面を考えます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/92ef1f2d-6dc7-857b-98f0-9bf1c17085a6.png)

ここで赤色のマス(1列目・4行目)について考えると、いずれの「ブリッジのレンズ」も、このマスを取って「ブリッジのレンズ」の一部にできないだろうなー……というのは少し想像すれば分かるかと思います。
塗りつぶしを増やして強引に取っても、「ブリッジのレンズの両端は線対称で、他の(孤立していない)レンズとくっつけない」ルールに反してしまうからです。

その上、ルールから、どの「ブリッジのレンズ」にもくっつくことができない「孤立したレンズ」は盤面に残せませんので、この赤色のマスは必ず空白マスなのです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/fb24779e-b146-bcf9-dc1c-a97035c792ae.png)

このような推論を行うと、他のマスもどんどん空白マスだと確定できます。先ほどの状態から、ここまで盤面を埋めることができました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/4b3064c6-3af1-ab15-3301-5201fc388fb8.png)

---

さて問題は「どうやって赤色マスなどの『どのブリッジからも塗りつぶせない位置のマス』を決めるのか」です。
思案した結果、次のような作戦を思いつきました。

### 1. それぞれの「ブリッジのレンズ」について、最大限伸ばせる範囲を決める

例えば左上のブリッジにおける、左側の「ブリッジのレンズ」の最大範囲はこんな感じ(橙色で塗ってます)。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/40a9d599-eee0-42c7-b9b1-0dc071bf2088.png)

また、左上のブリッジにおける、右側の「ブリッジのレンズ」の最大範囲はこんな感じ。
どちらも、「他のレンズとぶつからない」「空白マスの設定は尊重する」「孤立したレンズは飲み込んでOK」という条件下で塗っています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/ad603f88-cd33-e05a-46aa-05a775f6aa7b.png)

### 2. 各ブリッジの両端のレンズについては、「線対称である」条件から、実際に塗れる領域が狭まる

手筋の段では「どちらかでも塗ってたら塗れる」スタンスでしたが、それは確定事項だからであって、今回の場合は「どちらでも塗ってないと塗れない」になります。それぞれ、ここまで塗れる範囲が狭まりました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/77dae521-ced4-7369-cbc0-86d9024e369a.png)

### 3. そもそも、各ブリッジについては、「線対称の軸部分のマス」は塗れない

ブリッジ両端のレンズが線対称になる＆くっつけないルール上、その線対称の軸におけるマスは塗れません。
ただ、「線対称の軸」の定義が地味に分かりづらいので、以下に例を示します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/8b0244af-7ba0-7863-b92b-fc7a70087b27.png)

このルールにより、前述のブリッジ両端における、「最大限伸ばせる範囲」はこんな感じになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/c325ec02-6a52-8fa9-4f52-8a48f7aacbfc.png)

### 4. 全ての「ブリッジのレンズ」における「最大限伸ばせる範囲」をマージしたものを求め、そこから「どのブリッジからも塗りつぶせないマス」を逆算する

マージしたものがこれで、

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/5e6abd9e-f8a8-a800-62b7-9ce82651646c.png)

そこから逆算したものはこれ。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/4b3064c6-3af1-ab15-3301-5201fc388fb8.png)

# 背理法の「矛盾」判定について

[現状の実装](https://github.com/YSRKEN/puzzle_sunglass_solver)では、次の2つだけ実装しています。

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