meowdoku のソルバーを作った
ドパガキなので、動画広告に出てくるようなアプリが好きで、サーヤしかやってない謎ゲーム とかのシリーズが大好きだ。
いつもどおり動画広告を眺めていたら流れてきたのが meowdoku というネコ配置パズルだった。
meowdoku は N×N の盤面にネコを置くパズルで、ルールはこう。
- 各行・各列にちょうど 1 匹
- 各色領域にちょうど 1 匹（色数 = N のとき）
- ネコ同士は上下左右斜めに接触不可
さて、しばらく遊んでいると、盤面が大きい面で詰まる。
ゲーム内にはお手つき 3 回まで（それを超えると失敗）という制限があるので、当てずっぽうで置いていく総当たりでは押し切れない。
詰まると下のヒントボタンに手が伸びるが、これを押すには動画広告を最後まで見る必要がある。
見るくらいなら自分で組んだ方が面白いと思って、ソルバーを書いた。
仮定と巻き戻し（バックトラック）を繰り返せば、総当たりでも解ける。
ただしそれだと途中経過に何も残らない。
ルールが尽きたときだけ仮定に落ちる形にした。
ルールに則った消去法
適用するルールは 6 種類。強い順に一つずつ試し、当てはまれば適用してまた先頭に戻る。
- 残り 1 マスの領域・行・列に置く
- 色候補が 1 行（1 列）に閉じ込められているなら、その行の他色セルを除外
- 行（列）の候補が単色なら、その色の行外セルを除外（厳密モード）
- Naked K-subset — K 色の候補列 union が K 列に収まるなら、その K 列の他色セルを除外（Hall の結婚定理を色⇔列に適用）
- 「ここに置くと行・列・色の置き場が消える」セルを矛盾として除外
- どの推論も進まなくなったら候補最少の行または色で仮定し、矛盾したら巻き戻す
いくつか試した限りでは、6 の仮定に落ちずに一意解までたどり着ける盤面が多かった。
盤面が大きくなっても 1 〜 5 が最後まで通れば、人間が追える手順のままで解ける。
ちなみに、このルール構成は LinkedIn の Queens と同じ系統だと LLM が教えてくれた。
Queens の盤面を並べて見比べたら、確かに一緒だった。
再現性
総当たりの結果には「解けたのは分かったが、どうすればよかったのか」が残らない。
ルールベースで解くと、各ステップに「なぜその手が確定したか」を理由として残せる。
ソルバーは各ステップに盤面スナップショットと日本語の理由を記録する。
たとえばこういう形。
- 「色 3 は 3 行目にしか置けないため、3 行目の他の色のセルを除外」
- 「(4, 7) のネコにより、同じ行・列・隣接セル・同色セルを除外」
ビューアはこの記録を 1 手ずつ再生する。
◀ ▶ ボタン、スライダー、自動再生、任意の手番へのジャンプに対応した。
自分で解いていて詰まった盤面をソルバーに食わせ、1 手だけ進めれば、そこから先は自分で解ける。
ゲームの楽しさを残す
全部自動で解いてしまうと考える楽しさが失われる。想定している使い方は二通り。
- 完全ヒントとして、詰まった時に最後まで解いてもらう
- 1 手ヒントとして、次の確定手だけを見て自分の頭で追う
本命は後者だ。
ステップを 1 手だけ進めて盤面を確認し、その理由を自分でも当てられるようになれば、次から同じパターンには気付ける。
スクショから盤面を取り込む
盤面を手入力するのは面倒なので、ゲームのスクショを読み込めるようにした（js/cv.js）。
- 彩度の高いピクセルの行・列ヒストグラムで盤面のバウンディングボックスを検出
- セル間の白い隙間を数えて N を推定
- 各セルを 9 点サンプリングし、白い ✕ マークやネコの顔は彩度フィルタで弾いて代表色を出す
- 貪欲クラスタリングで色を領域ラベルに変換
- 平坦度（中央部が代表色と一致する割合）が低いセルは、確認警告を出す
ネコを置いた後のスクショでも動く。タイル背景がセルの色として残っているので、ネコの顔だけ避けて色を抽出できる。
まとめ
https://cat-solver.sougen.dev で動いている。
スクショから盤面を読み込み、ルールベースで解いて、1 手ずつ再生する。
良い meowdoku ライフを。