韓国で「037」という屋号で、一人でアプリを作っている Jaewon です。Chesspy という、チェスの駒で数字をぴったりにする毎日のロジックパズルを出しています。
前回の Zenn の記事では「サーバーなしで全員が同じ盤面を作る」話を書きました。今回はその続きで、作った盤面が本当に推理だけで解けるのかを、どう判定しているかをコードに沿って書きます。Web版も同じ TypeScript のコードで動いています。
ルールのおさらい
- 数字のマスは、ちょうどその数の駒から攻撃されるようにする
- 0 のマスは攻撃されてはいけない
- ルークは縦横、ビショップは斜めに、盤の端まで攻撃する（ほかの駒も貫通）。ナイトはL字
- 数字のマスには駒を置けない
ソルバーは「仮置き」をしない
ソルバーは空きマスごとに「まだあり得る駒の種類」の集合を持っています。最初は全部の種類が入っていて、推論が進むたびに消していきます。集合が空になったマスは空きで確定です。
大事なのは、試しに置いてみて矛盾したら戻す、という処理を入れていないことです。使えるのは次の4つのルールだけで、どれも盤面から確実に言えることしか書き込みません。全マスが確定すれば解けた、途中でどのルールも効かなくなったらその盤面は不採用です。
ルール1（0のマス）
0 を攻撃できる位置から、その駒を候補から消します。同じ行・列ならルーク、斜めならビショップ、L字の位置ならナイトが消えます。
ルール2（数字ひとつを見る）
- その数字がもう満たされているなら、ほかのマスからその数字を攻撃する駒を消す
- その数字を攻撃できるマスがちょうど n 個しか残っていないなら、全部に駒が入る
- 足りない攻撃の数と、まだ置いていない駒の数が同じなら、残りの駒は全部この数字を攻撃するしかない。届かないマスは消す
ルール3（盤全体の数）
駒が全部決まったら残りは空き。候補が残っているマスの数が駒の数と同じなら、全部に駒が入る。ある種類を置き切ったら、ほかのマスからその種類を消す。
ルール4（種類ごとの数）
ある種類が入れるマスの数が、その種類の残りの数と同じなら、全部その種類です。
アプリの「ヒント」も、この同じルールを1つずつ文章にして見せているだけです。
例題を、ソルバーの順番で解いてみる
Zenn の記事に載せた例題です。駒はルーク1つとビショップ1つ。
A B C D
1 . 2 . 0
2 . 1 . .
3 . 1 . .
4 1 . . .
- ルール1：D1 の 0 を見ます。1行目と D 列にはルークを置けません。斜めの C2 にはビショップを置けません。これで A1、C1、D2、D3、D4 はビショップだけ、C2 はルークだけが候補に残ります。
- ルール2：B1 の 2 を見ます。駒は全部で2つなので、2つとも B1 を攻撃するしかありません。B1 に届かない候補は全部消え、残るのは A2（ビショップ）、D3（ビショップ）、B4（ルーク）だけになります。
- ルール2：A4 の 1 を攻撃できるのは B4 のルークだけ。ちょうど1マスなので、B4 はルークで確定です。
- ルール2：B3 の 1 は B4 のルークで満たされました。A2 のビショップは斜めに B3 を攻撃してしまうので消えます。
- ルール3：候補が残っているのは D3 だけで、残りの駒も1つ。D3 がビショップです。
実際にソルバーにこの盤を渡すと、解とあわせて「手数5、最大ルール3」が返ってきます。
盤面の作り方
- 日付から作った乱数で、駒の数・種類・位置を決める（種類は2つ以上混ぜる）
- 駒のない全マスに、攻撃されている数を書く。この時点では数字だらけの簡単な盤
- 数字をランダムな順に1つずつ消してみて、消してもソルバーが解けるなら消したままにする
- 消した数字をいくつか戻す（序盤の盤は1〜2個、6×6 の後半からは0個）
- どの数字からも攻撃されていない駒があれば、その駒が攻撃しているマスの数字を1つ戻す。最後の1個が数合わせだけで決まる盤にしないためです
- 最後にもう一度ソルバーにかけて、手数と最大ルールが決めた範囲に入っているかを見る。さらに総当たりで2つ目の解がないかも探す
ルールが正しければ、推論だけで解けた時点で答えは1つのはずです。それでも実装ミスに気づけるように、総当たりのチェックは残しています。300回試して条件に合う盤が出なければ、シードを1つずらしてやり直します。
難しさは「最大ルール」と「手数」で決めている
ステージごとの条件はこうなっています。手数は、ルールが効いた回数です。
| 盤 | サイズ | 駒の数 | 手数 | 最大ルール |
|---|---|---|---|---|
| 1〜2 | 3×3 | 1〜2 | 1〜8 | 3 |
| 3〜5 | 4×4 | 2 | 2〜10 | 3 |
| 6〜9 | 5×5 | 2〜3 | 4〜12 | 3 |
| 10〜13 | 5×5（ナイト入り） | 3 | 6〜14 | 3 |
| 14〜17 | 6×6 | 3〜4 | 6〜16 | 4 |
| 18〜20 | 6×6 | 4〜5 | 8〜18 | 4 |
| 日曜の後半など | 7×7 | 5〜6 | 18〜30 | 4 |
種類ごとの数を数えるルール4は、6×6 になるまで出てこないようにしています。
これから見たいこと
Reddit で「サイズではなく、必要な一番難しい推論で盤を評価してはどうか」という意見をもらいました。上の表のとおり、生成のときにはもう最大ルールと手数で絞っています。ただ、それが本当に体感の難しさと合っているかは、まだ確かめていません。続けて「その指標と実際のクリア時間を比べてみては」とも言われて、なるほどと思いました。見通しのいい 6×6 が、長い連鎖のいる 4×4 より早く解けることもあるので、ここはこれから見ていくつもりです。
さいごに
Chesspy は iPhone 版が無料・広告なし・アカウント不要で、ブラウザでもそのまま遊べます。
「この盤は推理だけでは無理だった」というものがあれば、日付と盤の番号を教えてもらえるとうれしいです。