人間に近い解き方をして解き筋を表示するソルバーを作りたい＋α
この記事はペンシルパズルI Advent Calendar 2022 18日目の記事です。
今年こそちゃんと時間をかけてわかりやすく書こうと思ったのに今年も前日に下準備も案出しもなしに書き始めてしまったので雲行きが怪しい。(ここまで書いた時点で12/17 04:35)
0.まえがき
長いので読み飛ばしたい人は1.3と1.4と4だけ読めば十分です。
1 人と機械のソルバーの分析
1.1 人と機械の解きチェック
ペンシルパズルの問題を人手で作問するとき、作者にとって唯一解の確認は（大抵の場合）結構ウェイトが大きいかと思います。それでいて人間である以上チェックに見落としもつきものなので間違いのないチェックをしてくれるソルバーがある・いるととても大きな助けになります
完全に機械的なプログラムのソルバーで最終的な解きチェックを行うと、たいていのソルバーの場合はその解答を示してくれる、ものによっては推定レベルを表示したり解き筋を表示したりもしてくれます。解きチェックとは少し違いますがエディタにソルバーを紐づけてリアルタイムに解答を表示するものもあります。
では人間のソルバーにチェックをしてもらった場合はどうでしょうか？
人間のチェックでは解き筋の提示や推定のレベル提示は機械と同じくできるでしょう。チェックのリアルタイム性はさすがに限度がありますね。正確性について機械より劣る、解きスピードが遅いということもあるでしょう。
上記のように人間は機械的ソルバーに劣る点もありますが、機械的ソルバーに対して優位に立つ部分もあります。例えば解き筋の見つけやすさや作者自身が気が付けない解き筋の穴など、パズルを人が実際に解いたときのパズルとの相互作用：動きの分析については機械的ソルバーに対して大きな優位性があるのではないかと思います。（動きについては私の2年前の記事を参照：読んであると1.1~1.3で言っていることについて裏で何を考えているのか少しわかります）
この記事を書いた動機として、そのような人間のソルバーならではの優位性をできるだけ機械のソルバーに持たせて作問の利便性を上げたい・コンセプトとできることの実装例を示したい、というものがあります。
1.2 機械的ソルバーの特性
機械的ソルバーの強みであって弱みでもあると思うのですが、人間的には見えずらい確定であってもすみずみまでもれなく探索し、確定箇所を見つけてしまうために人間の解き方とかけ離れてしまうことが間々あります。人間は視覚的に盤面をとらえて問題を解くため、どうしても目の行きやすい場所と行きにくい場所があったり、決まらなそうな箇所を無意識に避けたりと、機械が行うような漏れのない探索とは少し距離のある解き方をしがちです。また、機械は人間が通常行わないような数段の仮定を重ねる解き方に依拠して確定を得ることが多いです。それはソルバーに手筋のパターンを実装するコストが大きい、あるいはそもそもコストを度外視しても手筋の実装が難しい、ということがあります。
仮定の実装だけであれば比較的小規模のプログラムだけでどんな問題でも解けるところまで到達します。一方、手筋を実装するとなると手筋一つ一つに個別の実装が必要となり、人間が無意識に使用する手筋をすべて用意しようと思うとそれだけで大きなコストとなります。また、少し盤面の見る範囲が広くなる二次元的な手筋や機転を利かせる必要のある手筋だと人間的には簡単であってもソルバーに実装するのが難しいということもあります。
例えばループパズルの小ループ禁は、線のつながっているすべてのマス/線の収まっている領域全体のマスを見てから（広い範囲の二次元的処理）更に小ループ禁の確定マスの部分に意識の焦点を持っていく（機転を利かせる）というプロセスで決まったりしますが、こんな基本的な手筋でも実装するのは結構難しいです。人間であれば2次元に網を張った情報を一度に処理できますが、プログラムの1次元的な記法では2次元的に網を張って情報交換するような処理を記述するだけでも難しく、特定部分に注目するまでの曖昧なプロセスを厳密なルールのある言語で記述するのも難しいです。
長くなりましたが、要するに仮定のプログラム実装は比較的楽！でも手筋実装はめんどい！そもそも実装むずすぎ！
⇒機械のソルバーが仮定メインになって人間的解き方と違いが大きすぎる！
ということです。
以降「ソルバー」と言えば機械のソルバーを指すこととします。
1.3 人の解法の特徴例
ソルバーに人間味を持たせた解き方を実装することを目標としていますが、まずは実装対象となる人間味のある解法の特徴をいくつか例示します。
①確定がわかったとき、その確定から優先してわかる場所を考える
ソルバーがマスを並び順に処理していくのとある程度は近いですが、図の橋をかけろのように盤面上での距離が離れたところに確定が行くことがあるのでこれはマスの並び順では表現しきれません。これを実装できると情報が増えたところを優先的に調べられるので手が進みやすくなり、ソルバーの高速化につながりそうです。
②一度調べた進まない個所を何度も調べない
人間的には無意識にやっていると思います。あまり細かく言うこともないでしょう。とはいえソルバーとしては実装に注意しないと手筋適用の確認が無意味な箇所に何度もチェックをしてしまいます。これは人間味というよりはソルバーの無駄を省く方向に影響しそうです。無駄か無駄でないかの基準をどのように実装するかがポイントです。
③手筋の確認に優先順位がある
手が進む箇所を調べるとき、最初から難しい手筋を使うのではなく、まず調べられるだけ簡単な手筋で進むところを探すと思います。（難しい手筋とは、たとえばヤジリンにおける市松など）
これは特に意識しなくても手筋を乗せたソルバーであればプログラムの書き順だけで勝手に適用されるかもしれません。注意点として、一か所に対して簡単な手筋→難しい手筋の順で適用可能性を調べるというよりは盤面全体であるレベル以下の手筋を調べた終わった後に盤面全体に難しい手筋が使えるか探す、という順番の方がより人間的になりそうです。適用できそうな難しい手筋であれば積極的に使う、というレベルにまで順序性を求めると「できそう」という部分のあいまいさを手筋ごとの定義してやる必要がありソルバーへの実装は難しそうです。
④知識レベルによってそもそも使える手筋が制限される
これも当たり前と言えばそうですね。ソルバーの解答力を制限する、という意味では⑤の先読み制限にも通じるところがあります。
⑤仮定の中でも先読みを基本的には使用する
先読みの定義とは？となりそうですが、多くの場合は一段階の仮定と手筋だけで確定を発見することとして説明がつくのではないかと思っています。また、一段仮定の中でも脳内のワーキングメモリで処理できる手数、という制約も先読みでは付いてきそうです。
一段仮定を優先すると処理する分岐、ループが減ることでソルバーの高速化にもつながる可能性もあるでしょうか？また、ワーキングメモリには個人差があるので先読みの深さを指定できると解き筋における人間味の度合い調整、難易度推定の基準調整などもできそうです。
⑥進まなそうな箇所では仮定をすぐ打ち切り、多段仮定は行わない
進まない空間に突然何かを書いてみるような仮定、または更にそこに仮定をもう一段重ねるようなやり方を最初からやることは人の場合少ないと思います。
実装できると⑤と同様時間のかかる探索を避けて高速化にもつながりそうです。
他にも特徴はあるとは思いますが、とりあえずはこれくらいにしておきます。実装方針が立つものについてのみ言及している気がしますが、曖昧で言語化しにくいものは思いついていないと思いますので何かあればツイッターで独り言してもらえると今後の実装方針が増えて喜びます。
1.4 人間的解法のソルバーへの実装方法
ここでは1.3で見た①～⑥を具体的にプログラム上に実装する方法を概要レベルで考えてみます。
①確定がわかったとき、その確定から優先してわかる場所を考える
これは、ある確定があったときに確定の可能性が発生する範囲を明確に定義してやり、調査対象候補をキューに追加してキューを上から処理していくことで定義できそうです。単に変化があった場合、ではなく特定の変化があった場合に絞れるとなおよさそうです。
②一度調べた進まない箇所を何度も調べない
これは前述の③のキューに投げ込むタイミングで調査可能な状態にフラグを切り替えればよさそうです。同じ対象が複数回キューになげこまれることがあるので、一度調査が完了したらフラグを落としておくことで繰り返しの調査を回避できます。前述の二次元的であいまいな手筋などでこの切り分けを実装するのは難しいのである程度は妥協します。
③手筋の確認に優先順位がある
やり方はいろいろある気がしますが、内側に優先順位の高い手筋群のループを、外側に優先順位の低い手筋のループ群を記述してとりあえずレベルのが実装できます。優先度が低いもので進んだらいったん最優先の手筋群に戻る構造です。
④知識レベルによってそもそも使える手筋が制限される
手筋ごとに使用可能フラグを設定するだけで実装できそうですが、手筋数分用意するのは面倒なので今のところはやっていません。
⑤仮定の中でも先読みを基本的には使用する
仮定を実装するとき、一段仮定の使用と多段仮定の使用を別処理として切り出し、先読み側では再帰的な仮定メソッドの呼び出しを制限し、多段では仮定メソッドの再帰を許可するような構造を作ればよさそうです。
⑥進まなそうな箇所では仮定をすぐ打ち切り、多段仮定も行わない
これは①を仮定に組み合わせることで実装できそうです。具体的には、仮定を一手行ったとき、①で記載した特定の変化に起因するキューの追加が発生する場合のみ仮定を先に進めることで実装できそうです。
2 ソルバーの実装(橋をかけろ）
実装した橋をかけろソルバーのデータ構造や処理構成を記載します。
特有のものになっているところはありますが他のパズルに応用できる所もあると思います。
細かい手筋の話は、適当に飛ばし読みしてください。
2.1 データ構造
2.1.1 基本構造
・Numクラス
一つの数字ヒントの手筋適用に必要な情報を管理するクラス。
各方向に引いた本数、自身の残り本数、周囲の数字に引ける残り本数、周囲の数字が行き止まりかといった情報などを管理する。Numクラスで完結する手筋はここに実装される。
・Emptyクラス
その空白マスの周囲4方向の数字を管理するクラス。
線がマスに引かれた際に周囲の数字を取り出すためだけのクラス。（線を引いた引かないは特に管理しない：Numクラスに周囲の残り本数を管理させているため不要）Empty単体では手筋は判断できないので手筋は実装されていない。
・Islandクラス
その島に所属する数字を管理するクラス。
所属している数字ヒントのリストに加えて、まだ引き終わっていない白の数字のリストを分けて管理している（図で灰色になっていない白い数字）。ひとつながり関連の手筋を調べる際に情報を取得するために使用する。最初は全ての数字が別の一つの島として設定され、線が引かれるごとに島がマージされていく。Island単体では手筋は判断できないので手筋は実装されていない。
・Boardクラス
盤面の全体を管理するクラス。線を引いた時に発生する情報伝達はここで管理する。解答ロジックの基本と上記複数のクラスから情報を取り出して組み合わせる手筋はここで管理する（分けてもいい気はしている）。あまり重要ではないですがNumクラスは仮定深度＋xy座標の3次元配列ではなく仮定の深度と数字IDだけで解き進める上では管理します。座標関連の情報はEmptyクラスなども使って各クラスのプロパティに持たせているのでほぼ不要となります。こうしたほうがメソッドの適用対象を簡単に取り出せるので便利です。
2.1.2 仮定のデータ構造
仮定なんてただ仮定一段階するたびに盤面複製するだけじゃないの？と思うかもしれませんが、NumクラスとIslandクラスの情報が若干多いのでいちいち複製していると仮定をするときには解答処理の全体を通して見ると処理の無駄が増えます。ほとんどの仮定は無駄打ちに終わるので、そのために全部を何度も複製するのはちょっとコスパが悪い。そのため必要な情報だけ適宜複製します。具体的にはNumやIslandのパラメータを更新する必要があるときに更新対象だけを仮定段階用に複製し、更新対象外の複製していないものはその前の仮定段階と同じものを参照します。手筋を調べるだけなので前の段階と実質が同じものでも困ることはありません。仮定が終わったらそのレイヤーを捨てるだけで後始末が完了することも変わりありません。
以下はイメージ図。
青と緑が記入対象になると黄色〇を作る
2.2 解答処理の実装
1.4で書いたことはそのままなので特に書きません。
橋をかけろの手筋的な話になるので読み飛ばしてOK
2.2.1 数字手筋について
橋をかけろを解き進めるとき、複数数字ヒント同士の比較で手筋適用が決まりますが、基本手筋を考えるうえでは数字の全情報がなくても決定できます。例えば左右に並んだ数字ヒントで手筋適用を見るとき、それぞれの数字の上下方向の情報は不要です。実は向き合う数字に向けて引ける線の残り本数と行き止まり情報しか必要ありません。ということで必要な情報だけを更新される度に線で結ぶ対象（候補）の相方に渡しておけば一つの数字ヒントだけで基本手筋は完結します。また、この更新があったときに1.4で触れたキューに手筋調査候補の数字として追加されます。
数字手筋の実装は実際の人間の解き方をプログラム用に置き換えています。人間は表出数字に加えて引かれている本数を認識して解きますが、実は元の表出数字の情報は不要で残り本数だけで手筋を考えられます。以下の図の三つの色付き数字は手筋を考える上では二方向が残り本数2、自身の残りは2本、残り引き本数が0の方向は行き止まり、として見ればすべて同じ状況です。
線は引かれているが行き止まりではない、線が引かれていて残り引き本数がまだある、など周囲の数字も含めて細かい場合分けはありますが、やはり表出数字は気にせず残り本数とそれらの状況の組み合わせだけで手筋が決まります。
方向と上記パターンの組み合わせは手筋の選択には関係ないので、判定は4方向がどのパターンに当てはまるかをカウントして適用される手筋を導出し、どのパターンの方向に線を引くか、として手筋の適用結果も導出します。上述の残り本数による捨象などで手筋判定ロジックは結構グルーピングしてますがそれでも決まるパターンだけでプログラム上35種類くらい、決まらないパターンも判定するのでそれを含めるともっとあり実装がめんどい、デバッグがきつい。（このパターンの多さが橋をかけろ手筋集で先読みで確定を判定してやりながら手筋を覚えたほうがいいとしている理由です。上図の三つのパターンが手筋チェックしたい数字の周りにあったときには4方向それぞれ同類判定が必要で、同類判定の種類は上記以外にもあり、このような数字ヒントのステータスパターン認識と適用される手筋のパターン認識を最初から正しく判断するのはちょっと厳しい）
デバッグ結果の書き戻しをまだしていないのでもうちょっと増えそう
2.2.2 ひとつながり系手筋
Islandクラスから残り本数が0出ない数字を取り出し、その数が1個,2個と少なければその数字で行き止まりが発生しないように手筋を適用したり、その数字と隣接する数字に行き止まりとして通知して手筋調査対象のキューに追加したりします。
2.2.3 カウント系手筋
一部ですがカウント系の手筋も実装しました。手筋自体から説明が面倒で実装は更に面倒なので説明は省略します。（じゃぁこの項は何なのか）
2.2.4 線引きロジックと手筋チェックキューの追加
橋をかけろの基本手筋は進む可能性がある/ないの状態変化の境界が明白です。基本的には線を横に引かれて片側が行き止まりになった場合と隣接するヒント数字に引ける残り本数が1以下に減った場合のみです。これに当てはまらない状態変化は無視します。また、通知先の数字が意味のない情報と判断すれば（すでに分かっている情報から変化なしとわかれば）キューには追加しません。イメージ図は下記参照。
3 完成したもの
(UIなどは細かすぎる話なのといろいろ改善中なので今回は割愛。)
3.1 サンプル動画など
こんな感じ。（古い・・・）
実装したい手筋はまだまだ残っている状況ですが、パズスクの大抵の問題はゼロコンマ数秒とか簡単ならもっと短い時間オーダーで瞬殺してくれるようです。思ったより早かった。アゼンなら一段階仮定（先読み）で、ハバネロだと3段～4段仮定指定くらいで解いてくれる。もっと手筋を充実させて自分の分身といえるくらいの知識と解き筋を人が参照できるように実装したい。誰得。
なお手筋バグがあるのが致命的なので修正が終わるまで公開しないつもりです。どうせ自己満企画ですし公開されているソルバーはもうありますから・・・
開発中でよければソースはこちら。計画0の思い付きで全部作っていたのでやはりデータ構造がよくなかったところがあり、作り直し中で散らかっています。
3.2 課題
結果表示の部分に問題があり、確定経過のログはとったものの、確定データの持ち方が悪く仮定で破綻させるまでの経過をうまく表示させられないです。何が問題かというと、仮定の中で正解パターンに当たったとき、残りのパターンがすべて破綻すれば正解パターンと破綻パターンをすり替えるようなことをやらないといけないのですがそれにデータの持ち方が合いませんでした。それと描画で仮定の各段階も開いてワンクリックで描画遷移するようなUI実装が間に合っていません。
4 .今後やりたいこと
ここまでですら作業が追い付いていないので本当にできるとは一ミリも思っていない。
4.1 リアルタイムソルバー
まずそもそもエディタを実装する必要はあるのですが。盤面の作成についてもすべてログを取り、各入力段階を選択してそこからソルバーの結果を重ねられるようなものを実装したい。ソルバーログの終点からヒント数字を追加していけるような実装もしたい。入力した解答を無視して解くか、入力した解答を加味して解くかも選べるとなおよい。
4.2 プレイヤー（エディタ）
何かペンパの問題を解いていて破綻したとき、既存のプレイヤーだと仮定のログは全て破棄されて一本道の情報しか残っていないので何を間違えたのかわからないので困ることがありますよね。枝分かれも含めてログをすべて取るデータ構造にすれば仮置きを毎回破棄する必要はなくなり、遡って間違いの分析をできます。競技でなく趣味として楽しむ範囲であれば更にツールが便利であってもいいでしょう。ということでそんなことができるように実装できればと思っています。
4.3 他力本願でやってくれる人がいたらうれしいこと
ぱずぷれという非常に便利な神ツールが公開されているものの、実はツールの特性に縛られて頭打ちになっている利便性はあると思います。
作問においてもワンクリックで各ステップの盤面を比較したり確定の足跡を振り返れると便利ではないでしょうか？作問中の盤面を保存するとき、データの保存形式を入力ログ形式とすれば過去の自分がどのようにその解答盤面に至ったかを振り返り、完成盤面と比べて解き筋が損なわれていないかを確認することもできます。解答経過を表示するリアルタイムソルバーを組み合わせることで想定解き筋の手順が壊れるようなヒントが配置されたタイミングを自動で確認することもできます。
盤面ではなくログに主眼を置くデータ構造とUIにすることでプレイヤーもエディタも利便性が格段に上がるのではないかと思っています。誰かぱずぷれを魔改造して汎用的なのを作って！お願いします！
5 あとがき
4.3の他力本願が裏の本題でした。
以上、ここまで読んでいただきありがとうございました。