ナンバーリンクを、4 段のソルバー内蔵でブラウザに実装した。この連作でいつも探しているのは「盤を見ただけで分かること」だが、今回はそれが手掛かりの配置そのものに現れた。盤を市松に塗るだけで、探索も部分解もなしに「この数字の置き方はそもそも解を持ちうるか」が判定できる。ソルバー内蔵パズル第 54 弾。
デモ: https://sen.ltd/portfolio/numberlink/
リポジトリ: https://github.com/sen-ltd/numberlink
ルール
- 同じ数字のペアを、縦横に隣接するマスの列（＝経路）でつなぐ
- 経路どうしはマスを共有しない。自分自身と交差もしない
- 盤のすべてのマスを使う
3 番はニコリのルールで、「点をつなぐゲーム」の多くはこれを落としている。もうひとつ、ニコリの盤は慣習的に「線が自分自身と並走しない」ように描かれる——同じ経路の 2 マスが盤上で隣接しているなら、その 2 マスは経路上でも連続している、ということ。これは普通、ルールではなく作法として語られる。本稿の後半で測ったら、作法ではなかった。
手掛かりの配置だけで決まる不変量
盤を市松に塗る。(r+c) が偶数のマスを黒、奇数を白と呼ぶ。
経路は縦横に 1 マスずつ進むので、必ず色を交互に踏む。だから m マスの経路について:
- 始点が黒なら、黒は
⌈m/2⌉マス、白は⌊m/2⌋マス - 終点が黒になるのは
mが奇数のときだけ
これを両端の色で言い換えると:
| 経路の両端 | 経路長 | 黒 − 白 |
|---|---|---|
| 両方とも黒 | 奇数 | +1 |
| 両方とも白 | 奇数 | −1 |
| 色が違う | 偶数 | 0 |
解では経路が盤の全マスを覆う。つまり全経路について上の ±1 を足し合わせたものが、盤全体の黒マス数 − 白マス数に一致する。経路に一切言及しない等式が残る:
（両端が黒のペア数） − （両端が白のペア数） = （盤の黒マス数） − （盤の白マス数）
右辺は h と w だけで決まる定数だ。面積が偶数なら 0、奇数なら 1。つまり:
偶数面積の盤では、両端が黒に乗っているペアの個数と、両端が白に乗っているペアの個数は必ず等しい。
これは手掛かりを一巡なめるだけで確かめられる。探索も部分解もいらないし、間違えて引き返す必要もない。実装は src/numberlink.ts の parityOf で 20 行ほど。デモページの右側にはこの勘定をそのまま出す小さなパネルを置いた。
テストは 3×4 と 4×4 の全分割 102,749 通りに対してこの等式を毎回検証している（違反 0）。npm run stats はさらに 2×3・3×3・3×5 を足して 137,789 通り。
必要条件であって、十分条件ではない
最小の反例は 2×3 で見つかる。両方の行の真ん中に数字を置く:
. 1 .
. 1 .
2 つの 1 は色が違うので勘定は合う。それでも解はない。上の真ん中のマスからどちらへ出ても片方の角が取り残されるが、角は隣接マスが 2 つしかないので経路の内点になれない——内点は次数 2 を要求するのに、行き止まりになってしまう。
ペアが 1 組だけの盤は、じつは古典問題そのものになる:
指定した 2 マスを端点とするハミルトン路は存在するか。
全マスを使い切る 1 本の経路 = ハミルトン路だからだ。そして上の色勘定は、格子グラフのハミルトン路に対する古典的な色条件そのもの。全配置を数え上げると:
| 盤 | 勘定が合って解あり | 勘定が合って解なし |
|---|---|---|
| 2×2 | 4 | 0 |
| 2×3 | 8 | 1 |
| 2×4 | 14 | 2 |
| 2×5 | 22 | 3 |
| 3×3 | 10 | 0 |
| 3×4 | 29 | 7 |
| 3×5 | 28 | 0 |
| 4×4 | 64 | 0 |
面白いのは単調ではないところ。2×3 に反例があるのに 3×3 にはなく、3×4 に 7 件あるのに 3×5 と 4×4 にはない。ギャップはサイズの関数ではなく、盤の形の関数だ。
「作法」が実は一意性のほぼ全部だった
生成器を書いていて気づいた。この連作の生成は答え先行——先に格子を経路に分割し、各経路の端点に数字を書く——なので、出てくる盤は定義上すでに解を 1 つ持っている。問題は「それが唯一か」だけ。
7×7 で分割をランダムに引いて、一意になる率を測った:
| 盤 | 引いた分割 | 並走を許した場合 | 並走を禁じた場合 |
|---|---|---|---|
| 7×7 | 各 800 件 | 0.0% が一意 | 72.8% が一意 |
| 9×9 | 各 300 件 | 0.0% が一意 | 58.7% が一意 |
800 件中 0 件と 583 件。これは作法ではない。
ただし交絡がある。並走禁止の経路は伸びにくいので短くなり、その分ペア数が増える。そしてペアが多い盤ほど易しい。なのでペア数を固定して比べ直した:
| ペア数 | 並走を許した場合 | 並走を禁じた場合 |
|---|---|---|
| 5 | 0.1% / 1274 件 | 40.0% / 55 件 |
| 6 | 0.0% / 1079 件 | 54.8% / 301 件 |
| 7 | 0.4% / 571 件 | 72.4% / 909 件 |
| 8 | 0.9% / 229 件 | 85.3% / 1153 件 |
| 9 | 1.3% / 77 件 | 89.9% / 936 件 |
効果はそのまま残る。生成器が並走禁止の分割だけを引くようにしたら、9×9 の盤バンクが数百ミリ秒で作れるようになった。それまでは 4000 回引いて 1 件も一意な盤が出なかった。
4 段のソルバーと、一度も発火しなかった段
ソルバーは経路ではなくマス間の辺を ON/OFF/未定で持つ。h*(w-1) + (h-1)*w 本の辺があり、パズルは 2 つの制約に分解される:
- 次数: 数字マスは ON の辺がちょうど 1 本、それ以外のマスはちょうど 2 本
- 形: ON の辺が作るのは閉路のない経路の集まりで、各経路の両端の数字は一致する
「全マスを使う」というルールがどこに行ったかというと、次数の側に丸ごと吸収されている。次数 2 のマスは定義上すでに誰かの経路の途中だからだ。ルールを 1 行に潰せたのは気持ちがよかった。
段は 4 つ:
-
deg— 次数だけ。ON が必要数に達したら残りを OFF、ON + 未定が必要数ちょうどなら未定を全部 ON -
chain— Union-Find で ON の連結成分を追い、閉路を閉じる辺と、異なる数字の鎖を溶接する辺を OFF にする -
reach— 連結性。各ペアの両端がまだ到達可能で、数字を 1 組も含まない領域が孤立していないこと -
probe— 未定の辺を片方ずつ仮置きして、矛盾する方を潰す
空盤からの決定率:
| 盤 | deg |
chain |
reach |
probe |
|---|---|---|---|---|
| 7×7 | 8.4% | 76.7% | 76.7% | 100% |
| 9×9 | 4.5% | 53.6% | 53.6% | 100% |
一意性の証明に要した分岐点の合計:
| 盤 | deg |
chain |
reach |
probe |
|---|---|---|---|---|
| 7×7（40 盤） | 3,306,784 * | 172 | 172 | 0 |
| 9×9（36 盤） | 10,800,036 * | 2,827 | 2,827 | 0 |
* 7×7 の 1 盤と 9×9 の全 36 盤が 30 万分岐で打ち切ったので、deg 行は下限。
そして reach の列を見てほしい。chain と完全に同じだ。決定率も、分岐数も、1 桁まで一致している。出荷盤・部分盤・ランダム盤を合わせて 2,488 回の比較で、reach が chain と違う結論を出したことは一度もなかった。
reach は「明らかに効くだろう」と思って足した段だ。効かなかった。次数勘定＋閉路禁止が連結性を含意する、という証明は持っていないので、これは定理ではなく測定として書くしかない。段はそのまま残してデモの選択肢にも出している——効かない段があることも成果物の一部だと思う。
「全マスを使う」を外すと、逆にほとんど何も変わらない
ナンバーリンクをナンバーリンクたらしめているのはルール 3 だ。外せば解の数が爆発するはず——と思って測ったら、しなかった:
| 盤 | 全マス使用なしでも一意 | 中央値の経路取り方数 |
|---|---|---|
| 7×7 | 36 / 40 | 1 |
| 9×9 | 31 / 36 | 1 |
出荷盤の 9 割は、「ただペアをつなぐだけ、空きマス可」と読み替えても答えが 1 通りしかない。定義の中核ルールが、この盤たちに関してはほぼ冗長になっている。
これは生成器の性質であってナンバーリンクの性質ではない。並走禁止の分割から育てた盤は過剰に決まっていて、一意性の縁ぎりぎりに立っていない。上の 0% 対 72.8% を裏から見た同じ事実だ。ぎりぎりで一意になっている盤なら、ルール 3 を外した瞬間に崩れるはずだ。
生成: 答え先行 + 分割修復
生成は逆走する。先に格子を並走のない経路に切る。それは「全マスを使う」の定義そのものなので、この向きからは違法な盤が原理的に出ない。ルールの検査は 1 行も要らない。要るのは一意性の確認だけ。
ここで効いてくるのが、ナンバーリンクには**「ヒントを足す」操作が存在しない**という点だ。手掛かりは経路の端点なので、数字を増やすことは答えの形を変えることに等しい。だから曖昧な盤が出たときは引き直さず、修復する:
- 解を 2 つ取る
- 2 解が食い違うマスを列挙する
- そのマスを通る経路を 2 本に切る（＝ペアが 1 組増える）
- 一意になるまで繰り返す
切る位置を食い違いの場所に寄せることで、余計な数字を撒かずに割り込みの解だけを殺せる。
格子そのものを数える
数字を抜きにして、h × w の格子を長さ 2 以上の経路に分割する方法は何通りあるか:
2xn: 1, 6, 26, 118, 528, 2364, 10580, 47352, 211928, 948504, 4245120, 18999440
3xn: 1, 26, 242, 3113, 34772, 412016, 4758383
4xn: 2, 118, 3113, 99636, 2993923
3 本とも OEIS には無かった（2026-09-04 時点）。2×n は
a(n) = 5a(n−1) − 2a(n−2) − 2a(n−3) + 2a(n−4)
を全項で満たす。4 項でフィットしたので 8 回の検証のうち 4 回は真の予測だが、証明は持っていない。
実装の教訓: 共有バッファが結論を裏返した
一番怖かったバグはこれ。「全マス使用なし」の経路取り方を数える再帰で、隣接マスを書き出す 4 要素バッファをパス長で添字した共有プールから取っていた:
const b = buf[path.length]; // ← これ
const m = neighbors(g, cur, b);
for (let i = 0; i < m; i++) { ... }
1 組のペアを繋ぎ終わると、次のペアが長さ 1 から再開する。そのとき buf[1] を書き潰すが、祖先フレーム（最初のペアが長さ 1 だったときのループ）はまだ buf[1] を反復している。数え落としが起きる。
このバグ入りで測った最初の結果は「7×7 の 40 盤中 6 盤しか一意でない、中央値 14.5 通り」だった。つまり**「全マス使用ルールが一意性を担っている」という、いま書いたのと正反対の結論**を出していた。記事の節が丸ごと逆になるところだった。
パズル側のテスト——盤が解けるか、解が一意か——では絶対に捕まらない。捕まえたのは、当たり前すぎて書くか迷った不等式テストだった:
it('is at least as generous as the full puzzle', () => {
// 全マス使用ありの解は、なしの解でもあるはず
expect(without).toBeGreaterThanOrEqual(withFill);
});
制約を外したら解が減った、という報告。フレームごとに 4 要素の配列を確保するだけで直った。
まとめ
- 市松の色勘定から、手掛かりの配置だけで閉じる不変量が出る。探索なしで盤の可否が判定できる
- 必要条件だが十分条件ではない。最小反例は 2×3、1 ペアの盤はハミルトン路問題そのもの
- ニコリが作法として語る「線が並走しない」は、一意性のほぼ全部を決めていた（0% 対 72.8%、ペア数を固定しても同じ）
- 連結性の段は 2,488 回の比較で一度も発火しなかった。証明はないので測定として書いた
- 定義の中核である「全マス使用」は、この生成器の盤に関してはほぼ冗長（36/40 が一意のまま）
- 全 74 テスト。辺で考えるソルバーと、辺を一切知らない分割列挙器の 2 エンジンが一致することを毎回確認している
デモ: https://sen.ltd/portfolio/numberlink/
リポジトリ: https://github.com/sen-ltd/numberlink