アラフ（Araf）を、4 段のソルバー内蔵でブラウザに実装した。盤を部屋に切り分け、各部屋はちょうど 2 つの数を持ち、面積はその 2 つのあいだに厳密に入る（2 と 6 なら 3・4・5 マス）。核心は 1 行の補題だ——答えの中で 1 マスを隣の部屋へ渡すと、他の部屋は無傷で、両方の部屋とも自分の 2 つの数を持ったままだ。だからルールが文句を言える点は「渡した側が床を割った」か「受けた側が天井を超えた」かしかない。ではマスを 1 つずつ交換したら? 大きさが両方とも変わらない。数は何も言えない。出荷盤で可能な交換 665 通りはすべて不正で、すべて「部屋が割れる」ことだけが理由だった。1 マス摂動 2,657 通りのうち 73.5% を殺しているのは連結性であって数ではない。ソルバー内蔵パズル第 60 弾。
デモ: https://sen.ltd/portfolio/araf/
リポジトリ: https://github.com/sen-ltd/araf
ルール
盤を部屋に切り分ける。
- 各部屋はちょうど 2 つの数を含む
- 部屋の面積は、その 2 つの数のあいだに厳密に入る。
a < bならa+1〜b−1マス - 部屋は辺で連結。すべてのマスがどれか 1 つの部屋に属する
以上。数は動かせないし、書き換えもしない。プレイヤーがやることは線を引くことだけだ。
短いルールだが、書いてある数と実際に効いているものが一致していなかった、というのがこの記事の中身になる。
まず、大半のペアはそもそも部屋になれない
部屋はちょうど 2 つの数を持つ。だから最初の問いは「どの 2 つの数が同じ部屋に入り得るか」だ。探索を始める前に、3 つの理由でペアを落とせる。
-
入る大きさが存在しない。
a < bが要求するのはa+1 .. b−1マスなので、b − a ≤ 1なら空集合。等しい 2 数は絶対に同じ部屋に入れない。 -
遠すぎる。 部屋は高々
b−1マスで両方の数を含むから、2 マスの距離はb−2歩を超えられない。 - 経路が第三の数を通るしかない。 部屋は他の数を飲み込めないので、経路は盤上の他のすべての数を避けなければならない。避けると届かないペアがある。
出荷している 72 盤でこうなる。
| 盤 | 数のペア | 大きさが無い | 遠すぎる | 第三の数で塞がる | 生存 |
|---|---|---|---|---|---|
| 6×6 | 236.5 | 77.0 | 66.6 | 53.3 | 39.7 |
| 8×8 | 692.0 | 225.9 | 286.6 | 98.8 | 80.7 |
合計 33,426 ペアが 4,333 ペア（13.0%） まで落ちる。
3 番目のスクリーンは書きながら「たぶん誤差だろう」と思っていた。部屋は小さいし、2 つの数のあいだに第三の数がちょうど挟まる配置なんてそう多くないだろう、と。単独で 5,474 ペア（16.4%） を殺していた。部屋が小さいということは、数の密度が高いということでもある。
1 マス動かすと何が起きるか
ここからが本題。完成した盤で、部屋 i のマスを 1 つ隣の部屋 j に渡す。
- 他の部屋は一切変わらない
-
iもjも、自分の 2 つの数はそのまま持っている（数のマスは動かさない） - したがってルールが文句を言える点は 2 つしかない。
iが床（lo）を割ったか、jが天井（hi）を超えたか
つまり、答えが 1 つしかない盤は、**可能なすべての 1 マス移動について「渡す側がすでに床にいる」か「受ける側がすでに天井にいる」**ことを要求する。
素朴に全部数えた。出荷盤上の 1 マス移動は 1,992 通りあって、すべて不正だった。
| 何が止めたか | 件数 |
|---|---|
| 渡した側の床 | 554 |
| 受けた側の天井 | 284 |
| そもそも部屋が 2 つに割れる | 1,287 |
（床と天井は同時に効くことがあるので合計は 1,992 を超える。）
交換は数に見えない
では、2 つの部屋でマスを 1 つずつ交換したらどうなるか。
大きさが両方とも変わらない。両方とも自分の 2 数を保っている。ルールには言うべきことが何も無い。アラフの語彙は部屋の大きさだけで、交換はすべての大きさを保存するからだ。
出荷盤で幾何的に可能な交換は 665 通り。すべて不正だった。そしてすべて、部屋が割れることだけが理由だった。数が止めた交換は 1 件も無い。
これは「数が止められない」のではなく「数には見えない」。答えを 1 つに絞る仕事のうち、この分は最初から幾何にしか担当できない。
だから硬さの 4 分の 3 は数ではない
入る前に取り違えていたのはここだ。盤に印刷されているのは数だけなので、答えを固定しているのも数だろうと思っていた。1 マス摂動を全部数えると、そうではなかった。
| 何が殺したか | 件数 | 割合 |
|---|---|---|
| 部屋の形（連結性） | 1,952 | 73.5% |
| 床または天井（数） | 705 | 26.5% |
| 合計 | 2,657 | 100% |
読むのは数だが、効いているのは幾何だ。
予算 —— ration
全体を縛る式は 1 本しかない。全マスがちょうど 1 つの部屋に入るので、部屋の大きさの合計は盤面積そのものになる。
Σ lo ≤ マス数 ≤ Σ hi
ソルバーは同じ不等式を「残り」に対して使う。まだ部屋を与えられていない数はそれぞれ部屋の半分ぶんなので、その数がまだ入り得る最も安い部屋と最も高い部屋が、残っているマス数を上下から挟む。これが ration 段で、ラダーの中で唯一グローバルな情報を持つ。
そして、盤が床から浮いている量と天井まで残している量の和がそのまま slack になる。これは生成器が一意性を保ったまま通せた「窓を 1 だけ広げる」操作の回数と、定義上ぴったり一致する。
1 マス補題の系がもう 1 つある。マスを渡せる部屋は、マスを受け取れる部屋の隣に立ってはいけない。立っていたら、その間のマスが動けてしまい、答えが 2 つになる。
出荷 1,074 部屋の内訳:
| 部屋の状態 | 件数 |
|---|---|
| 受け取れるだけ（床にいる） | 497 |
| 渡せるだけ（天井にいる） | 156 |
| 両方できる | 269 |
| どちらもできない（完全固定） | 152 |
| 規則を破っている隣接 | 0 |
ダイヤルは slack
生成器は難易度を設計しない。やることは 2 つだけだ。
- 部屋を先に描き、各部屋にその部屋を最もきつく記述する数を渡す。
size−1とsize+1——大きさをぴったり固定できる唯一のペア - その盤が一意なら、耐えられるだけ自由を返す。窓を 1 つ 1 広げてみて、まだ一意なら採用、そうでなければ戻す
下のダイヤルは 2 の検査を省いたものだ。「きつい状態では一意」な盤を取り、窓を k 回ランダムに広げて、まだ答えが 1 つかを見る。
| 広げた回数 | 6×6 で一意 | 8×8 で一意 |
|---|---|---|
| 0 | 120/120 | 120/120 |
| 4 | 55/120 | 56/120 |
| 8 | 14/120 | 20/120 |
| 12 | 12/120 | 5/120 |
| 16 | 1/120 | 1/120 |
| 24 | 0/120 | 1/120 |
| 32 | 0/120 | 0/120 |
| 48 | 0/120 | 0/120 |
出荷している 8×8 は平均 38.1 回ぶん広がっている。無検査でそこまで広げて一意が残る確率は 0% だ。だから生成器は試した 109.4 回のうち 38.1 回しか採用しない。
そして止まった時点で、すべての窓のすべての拡張が試されて拒否されている。盤は局所最大になっている。この主張は生成器の自己申告ではなく、出荷ファイルから読み直して npm test が再検証する。
偶然では出来ない
ランダムに部屋を描き、その周りに数を置き、ランダムに何回か広げる:
| 盤 | 広げた回数 | 枚数 | 一意 | 複数解 |
|---|---|---|---|---|
| 6×6 | 6 | 200 | 9 | 191 |
| 6×6 | 12 | 200 | 0 | 200 |
| 8×8 | 10 | 200 | 0 | 200 |
| 8×8 | 20 | 200 | 0 | 200 |
この作り方の盤は必ず 1 つ以上の答えを持つ（答えの周りに作っているので当然だ）。稀なのは一意性のほうで、8×8 では 400 枚引いて 1 枚も出なかった。
「あいだ」の読み違えは 2 通りあって、どちらもパズルを消す
「厳密に」を落とす。 閉区間に読むと、1 違いのペアも等しい 2 数も部屋を記述できるようになる。1 番目のスクリーンが止まる。
「辺で」を落とす。 部屋が角で繋がってよくなると、5 マスの部屋の形が桁で増える。
| 読み違え | 盤 | 候補部屋（正) | 候補部屋 | 生存ペア（正) | 生存ペア | 一意のまま |
|---|---|---|---|---|---|---|
| 閉区間 | 6×6 | 264 | 535 | 39.7 | 58.0 | 0 / 12 |
| 閉区間 | 8×8 | 731 | 1,788 | 78.3 | 121.1 | 0 / 12 |
| 斜め連結 | 6×6 | 264 | 2,106 | 39.7 | 81.1 | 0 / 12 |
| 斜め連結 | 8×8 | 731 | 6,937 | 78.3 | 179.0 | 0 / 12 |
サンプル 12 枚すべてが 2,000 解の打ち切りに当たり、一意なものは 1 枚も無かった。厄介なのは、意図した答えは両方の読みでも合法のままだという点だ。解いている最中は何も間違って見えない。2 つ目の答えがあると気づくまでは。
4 段のラダー
同じ「候補部屋カタログ」の上に 4 段。数字は、その段が単独で「このマスはどの部屋か」を言えるマスの割合。
| 段 | 6×6 | 8×8 |
|---|---|---|
pair — スクリーンだけ |
5.6% | 3.4% |
cell — 単位伝播（4 種） |
26.6% | 12.6% |
ration — 部屋を仮置きして残りマス数を勘定 |
100% | 100% |
search — 完全解法（exact cover） |
100% | 100% |
cell は 4 つの規則を不動点まで回す:
- あるマスを覆える部屋が 1 つしか残っていなければ、その部屋は確定
- ある数に使える部屋が 1 つしか残っていなければ、その部屋は確定
- ある数に残っている部屋の相方がすべて同じ数なら、その 2 数は結婚している。相方側の他の部屋を全部落とせる
- あるマスに残っている部屋がすべて同じ数のペアに属するなら、そのペアの部屋はこのマスを含まなければならない
面白いのは、広げる操作が難易度に効くところだ。広げる前（すべての窓が最もきつい状態）で採点すると、72 盤のうち 35 盤が cell だけで落ちる。出荷状態で採点すると 1 盤。slack がそのまま難易度になっている。
数え上げで列挙器を検算する
このソルバーで一番壊れやすいのは部屋の列挙器だ。連結集合を 1 つ取りこぼしても、落ちるわけでも例外が出るわけでもなく、ただ解の数が静かに間違う。
なので、空の盤の 1 マスに向けて列挙器を走らせ、固定ポリオミノ（A001168）を再現できるかを見る。10 マスの 36,446 まで一致した。重複列挙があれば多く出るし、取りこぼしがあれば少なく出る。どちらも一発で分かる。
ついでに、アラフの答えが住んでいる空間の大きさ——盤を辺連結の部屋に切り分ける総数——も出しておいた。正方形の場合は A145835 と一致する。
| 盤 | 切り分け方 | うち 2..5 マスの部屋のみ |
|---|---|---|
| 2×2 | 12 | 3 |
| 3×3 | 1,434 | 118 |
| 3×4 | 27,780 | 1,020 |
| 4×4 | 1,691,690 | 21,190 |
エンジンは 2 つ
スクリーンと ration は「速いが間違っているかもしれない」種類の最適化だ。だから両方持っていないエンジンで照合する。誰も所有していない最初のマスを取り、そこから伸ばせる連結集合を全部作り、たまたま数を 2 つ持って大きさが合法ならそれを部屋にして再帰する。何も考えない。
小さい盤で 60 枚、不一致 0。しかも一致するのは解の個数ではなく解の集合だ。同じ照合を閉区間の読み違えでも走らせている（スクリーンの挙動がまったく変わるので）。
テストは全 41 本。
まとめ
アラフの見た目は数のパズルだ。盤に印刷されているのは数しかない。
しかし数が語れるのは部屋の大きさだけで、大きさを保つ変形——1 マスずつの交換——は数から完全に見えない。答えを 1 つに絞る仕事の 73.5% は、最初から連結性が担当している。
Σ lo ≤ マス数 ≤ Σ hi という 1 本の不等式と、「渡せる部屋は受け取れる部屋の隣に立てない」という 1 行の系。この 2 つを持って生成器を書くと、難易度を一度も設計しないまま、局所最大の盤が出てくる。
デモ: https://sen.ltd/portfolio/araf/
リポジトリ: https://github.com/sen-ltd/araf