# meowdoku のソルバーを作った

2026-08-12

ドパガキなので、動画広告に出てくるようなアプリが好きで、[サーヤしかやってない謎ゲーム](https://www.youtube.com/watch?v=Jhq_KBPQnyM) とかのシリーズが大好きだ。
いつもどおり動画広告を眺めていたら流れてきたのが meowdoku というネコ配置パズルだった。

meowdoku は N×N の盤面にネコを置くパズルで、ルールはこう。

- 各行・各列にちょうど 1 匹
- 各色領域にちょうど 1 匹（色数 = N のとき）
- ネコ同士は上下左右斜めに接触不可

さて、しばらく遊んでいると、盤面が大きい面で詰まる。
ゲーム内にはお手つき 3 回まで（それを超えると失敗）という制限があるので、当てずっぽうで置いていく総当たりでは押し切れない。
詰まると下のヒントボタンに手が伸びるが、これを押すには動画広告を最後まで見る必要がある。
見るくらいなら自分で組んだ方が面白いと思って、ソルバーを書いた。

仮定と巻き戻し（バックトラック）を繰り返せば、総当たりでも解ける。
ただしそれだと途中経過に何も残らない。
ルールが尽きたときだけ仮定に落ちる形にした。

## ルールに則った消去法

適用するルールは 6 種類。強い順に一つずつ試し、当てはまれば適用してまた先頭に戻る。

1. 残り 1 マスの領域・行・列に置く
2. 色候補が 1 行（1 列）に閉じ込められているなら、その行の他色セルを除外
3. 行（列）の候補が単色なら、その色の行外セルを除外（厳密モード）
4. Naked K-subset — K 色の候補列 union が K 列に収まるなら、その K 列の他色セルを除外（Hall の結婚定理を色⇔列に適用）
5. 「ここに置くと行・列・色の置き場が消える」セルを矛盾として除外
6. どの推論も進まなくなったら候補最少の行または色で仮定し、矛盾したら巻き戻す

いくつか試した限りでは、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 ライフを。