遠い誓いソルバーを作った話と手筋集
この記事はペンパアドベント2020、8日目の記事です。
昨日の記事：へやわけ in へやわけ（yumaさん）
遠い誓いとは
遠い誓いというパズルがございます。ご存じない方のために簡単に説明しますと、盤面に向かい合う矢印を配置するパズルです。ルールを引用します。
太線で区切られたところ（国）にある１つのマスに、→←↑↓の矢印のどれかを入れます。すでに矢印が入っている国では、他のマスに矢印を入れてはいけません。
どの矢印にも、自分とペアとなる矢印が１つあり、たがいにタテかヨコの同じ列に入って向き合います。
辺を共有する国に、ペアとなる矢印を入れてはいけません。
ペアとなって向き合う矢印のあいだに、他の矢印が入ってはいけません。
（パズル通信ニコリ 131号 p110 より）
ペアになる矢印が属する国は隣り合ってはいけない、というルールが特徴的です。原作者ゲサクさんによれば、テーマは遠距離恋愛であるとのこと。10年ほど前にニコリのオモパコーナーに掲載されましたが、昇格することはなかったようです。
遠い誓いはオモパであるにもかかわらずぱずぷれ、puzz.linkといったプレイヤーに用意されており、インターネット上にも複数の作者によって出題されています。Puzzle Squareにも問題があります。およそ8割が自作ですが。
で、このパズルに魅了された私ウド、このパズルのソルバーを作りました。こちらから利用できます。ただ、全ての問題を解くことは出来ません。
方針
きっかけは17x17の問題を作っていて、複数解に気づかず投稿してしまったことでした。筆者はポンコツなので複数解をよく出します。みゃーみゃさんには足を向けて寝られないほどです。でも遠い誓いはマイナーなオモパゆえソルバーなんてものはない、じゃあ作っちゃえばいいじゃない。そんな安易な考えから制作をはじめました。
作るからには自分で使えるように作りたいと考え、軽く方針を決めました。具体的には、SATソルバーのような道具は使わず、すべて手筋を適用して解くこと、それから解いた過程を確認できることです。あわよくば難易度評価の手助けにしたいとの思惑もありました。
ソースは公開していませんが、jsファイル単体ですので、多少知識のある方なら見ることが出来ます。が、しかし非常に汚いですので、改造はおすすめしません。気が向いたらTypescriptでマシに書き直します……
手筋集
ソルバーに実装されている手筋を紹介します。
隣接禁
ルール文そのものです。とくに、矢印のすぐ先にある国には矢印は入りません。
禁止なのは「矢印が属する国の隣接」なので、このようなパターンもあります。
ですが、「矢印の先にあり」「国どうしが隣接している」なら、「矢印が入らない」とは限りません。以下を見てください。
相手探し
矢印の先に、ペア候補となるマスが一つしかない場合、そのマスにペアが入ります。
矢印の先に、ペア候補となるマスがなく、かつ逆向きの矢印がある場合、その2つの矢印はペアです。
これの応用で、ペア候補の矢印があり、ペア候補となるマスもあるが、それらが全て同じ国にある場合も、2つの矢印はペアです。
なお、間にある国が2つ以上の場合は確定はしません。
孤立の禁止
4方向すべてにペアとなる可能性のあるマスがない場合、そのマスには矢印は入りません。
残り物手筋
国に矢印の入りうるマスが一つしかない場合、そのマスには矢印が入ります。1マスしかない国が最もわかりやすいです。
また、残り物マスに向いている矢印があり、その矢印から見て残り物マスが最初のペア候補だった場合、残り物マスと矢印はペアです。
矢印の方向が確定しなくとも、「矢印が入る」という情報がヒントになる場合もあります。
国に複数のマスがあっても、矢印が入らないマスが確定することで、残り物手筋が適用できる場合があります。
予約の手筋
ある矢印のペア候補が、すべて同じ国にある場合、その国には矢印のペアが入ることがわかります。
これを利用して、その国を通る矢印が確定することがあります。
廊下の手筋
1xnマスの国を「廊下」とよびます。もとはへやわけ用語だったと思うので、いかした名前を募集しています。
廊下の短辺から廊下に矢印を向けることは出来ません。これは隣接禁からわかります。
逆に、矢印から見て最初のペア候補が廊下だった場合、その国のどこかにペアが入ります。
廊下のすべてのマスがある一つの方向しか向けないかつ、その方向が廊下の短辺であるとき、廊下を矢印と考えることでペアが定まる場合があります。
一見廊下ではない国でも、入らないマスをマークすることで廊下の手筋が使えるようになる場合があります。
勘の良い方は気づかれたかと思いますが、上記の残り物手筋はすべて廊下の手筋の特別な場合です。
チャラ男手筋
この節は現行のソルバーに実装されていないものです。
ある矢印Xから矢印の先を見たとき、一番最初に候補になるマスをYとします。「Xの候補のマスのうち」「Yと同じ国で」「Yと連続した」マスは、「矢印が入るとすればXのペアに限られる」という性質を持ちます。
予約の一種ですが、予約よりも弱い性質です。一番近くにいるマスの方向を限定することから「チャラ男手筋」と呼ぶことにします。今決めました。上記の手筋のうちいくつかの手筋は、この性質で説明できることがわかります。
廊下の手筋の項で出てきた、全てのマスがある1方向しか向けない廊下（以降の説明のため、「長い矢印」と呼ぶことにします）にもこの手筋は適用できます。
さて、次の盤面で、左上の2国に注目します。
この2国には次の2通りしか入り方がないことがわかります。
よってどちらのパターンでも、次のように「入りうる矢印」が決まり……
一部の矢印が確定します。
さて、これを「長い矢印」で考えましょう。チャラ男手筋において長い矢印は国である必要はなく、「1xn列状のマスに」「1つ（0でも2でもなく）矢印が入り」「すべて矢印がある1方向かつ短辺方向にしか向けない」という条件があれば適用することが出来ます。したがって、先に挙げた盤面は2つの長い矢印とみなすこともできます。
国の隣接条件もあるので盤面として等価ではありませんが、チャラ男手筋はこのような仮想の長い矢印にも適用することが出来ます。
このように複数の国を組み合わせて仮想の長い矢印を考えることで盤面が進む場合がありますが、なかなか機械に教えるのは難しいです。あと、この例はこのあとどう頑張っても唯一解にできません……
その他
ここで紹介したものが手筋のすべてではなく、複数の国の位置関係等からペアを決めていく問題なども存在します。試験的に実装しているものもありますが、問題によるところがあり、統一的な説明がしづらいので省略します。
おまけ：ユニークネス
遠い誓いではユニークネスが大活躍します(それだけ唯一解にするために苦労するということでもありますが……)簡単なものでは、辺に接する2マス以上の廊下の矢印の向きは確定します。
間違っても作る時に使わないでください。
作ってみて
「定式化を行わずに手筋で解く」というのは一見楽に思うのですが、プログラムを書くときにはエレガントとは無縁の泥臭い実装をしていく必要があります。このソルバーはどのような手筋で解いたかを出力する方針で作ったので、たとえば残り物手筋と廊下の手筋が本質的には同じものであるにも関わらず、分けて実装しています。人間にとってのわかりやすさは、プログラムの簡潔さや速度とトレードオフだなぁと感じています。
またこのソルバーには仮定を実装していません。これはただ単に技量不足によるものですが、それでも収集したほとんどの問題が解けています。これはおそらく、分断禁や2x2禁などのルールがなく見えない制約（と、それに由来する自明でない手筋）が弱いことを示していると考えられます。
また、手筋で解くことで難易度評価ができればいいな、との思惑が有りましたが、これは現在のところうまく行っていません。とくに孤立の禁止に顕著ですが、人間の感じる難しさには「見つけづらさ」が大きく影響しているからです。次の盤面を見てください。
プログラムはこの2つを同じ手筋で処理しますが、心理的な発見のしづらさは大きく異なります。このような「見つけづらさ」は機械的な評価に限界があり、難易度判定はまだまだ人間が解いてつけるしかないかなぁといったところです。
ちなみに
遠い誓いをSATソルバーで解くための定式化の手法はこちらで示されています。
またシェアウェアですが、Cross+Aというソフトが遠い誓いの自動解答に対応しているようです。すご。
明日の執筆者は斎藤すばるさんです。おたのしみに。
おまけ
遠い誓いの原作者ゲサクさんが自身のブログで出題している、「マイニチトイチカ」の全100題を、ぱずぷれに移植したものを公開……する予定だったのですが、著作権的に胸を張ってお出しできるものではないことがわかったので、お知らせするに留めます。ほしい人は筆者まで個人的に連絡をください。