ナンバーリンクを、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