Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
1
Help us understand the problem. What is going on with this article?
@YSRKEN

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

概要

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

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

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

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

作成したソルバー(Python製):

基本方針

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

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

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

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

使用した手筋

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

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

image.png

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

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

image.png

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

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

image.png

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

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

image.png

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

image.png

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

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

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

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

image.png

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

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

image.png

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

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

image.png

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

image.png


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

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

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

image.png

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

image.png

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

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

image.png

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

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

image.png

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

image.png

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

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

image.png

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

image.png

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

現状の実装では、次の2つだけ実装しています。

  • ヒント数字の条件をどうしても満たせない場合は矛盾
    • ある列/行について、「塗りつぶした個数」+「未定な個数」<「ヒント数字」なら矛盾
    • ある列/行について、「塗りつぶした個数」>「ヒント数字」なら矛盾
  • どのブリッジにも属せない「孤立したレンズ」が存在する場合は矛盾
    • 言い換えると、盤面内のレンズを全て検索し、その中で「孤立したレンズである」「周囲(上下左右)が全て空白マスである」ものを探す
1
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
YSRKEN

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
1
Help us understand the problem. What is going on with this article?