ヤジサンカズサンを解く — ソルバーが最初に学ぶことは、必ず嘘つきから学んでいる

ヤジサンカズサンを、5 つのルールセット内蔵でブラウザに実装した。矢印と数字の手掛かりは、自分のマスが塗られていないときだけ真でなければならない。塗られていれば、その数字は何を言っていてもよい。つまり手掛かりは嘘をついてよい。ソルバー内蔵パズル第 51 弾。

デモ: https://sen.ltd/portfolio/yajisan-kazusan/
リポジトリ: https://github.com/sen-ltd/yajisan-kazusan

ルール

H×W の盤面のいくつかのマスを塗る。

1. 塗ったマスどうしは辺で接してはいけない
2. 塗らなかったマスは全体で辺により 1 つに繋がる
3. 手掛かりは矢印と数字で、マスの中に書かれている。そのマスが塗られていなければ、数字はその矢印の向きに（自分より先、盤の端まで）ある塗られたマスの個数と一致しなければならない。そのマスが塗られていれば、その手掛かりは免除される ——何を言っていてもよい

ルール 3 がこのパズルの全部だ。手掛かりは盤面についての主張ではない。未知数のひとつ（自分のマス）を条件とする条件付きの主張だ。だから手掛かりは嘘をつける。ただし「自分が塗られている」という代金は払う。

言い換えると、ヤジサンカズサンの手掛かりは選言だ:

私は塗られている、または、私の数字は正しい。

対偶が本体

選言の使い道は対偶にある。数字のほうが絶対にありえないなら、残るのは左側だけだ。

長さ L の直線に塗られたマスは、接してはいけないので最大 ⌈L/2⌉ 個しか置けない。つまり ⌈L/2⌉ より大きい数字を書いた手掛かりは、どうやっても真になれない。よって:

言えない数字を書いた手掛かりは、自分のマスが塗られていることを白状している。

これは補助定理ではなく、このソルバーの一段目だ。測ると効き方がはっきり出る。出荷している盤面で、各段の不動点が盤の何割を確定するか:

サイズ	盤数	adj	cap	ray	white	probe
6×6	40	0.0%	32.4%	52.9%	59.6%	100.0%
8×8	40	0.0%	37.7%	58.0%	67.1%	100.0%
10×10	30	0.0%	34.2%	59.7%	64.3%	100.0%

adj（塗ったマスは接しない）が 0.0% なのは当たり前で、まだ 1 マスも塗られていないのだから隣接ルールには働きかける先がない。そして次の段——嘘を見つけること以外は何もしない段——でいきなり 3 分の 1 が決まる。

つまりこのパズルでは、ソルバーが最初に学ぶことは、例外なく嘘つきから学んだことになる。正直な手掛かりが仕事を始められるのは、嘘つきが誰かのマスを塗ってくれた後だ。

手掛かりは必ず足せる（存在定理）

まず土台。任意の合法な答えに対して、それを一意にする手掛かり集合は必ず存在する。証明は 2 ケースで、生成器のコードそのものになっている。

答えを A、殺したい別解を B とする。

ケース 1: A で塗られていて B で塗られていないマス c がある。
c に手掛かりを置く。A では c が塗られているので免除、数字は何でもよい。B では c が塗られていないので拘束され、B の実際のカウントと違う数字を選べば B は死ぬ。

ケース 2: そういうマスがない。 つまり A の塗りマス集合は B の真部分集合だ。
B にだけある塗りマス d を取る。ルール 1 より d の隣は B で塗られていない。d は A で塗られていないので、その隣も A で塗られていない可能性が高い——というのは雑で、正しくは読み順で議論する。A と B が食い違う最後のマスを d とすれば、d より後ろのマスは一致している。d の右隣（無ければ下隣）は B で塗られていない（ルール 1）かつ d より後ろなので A でも塗られていない。そこから d の方向に矢印を引くと、その直線上のマスは d 以外すべて一致するので、カウントはちょうど 1 だけ違う。A の側の正直な数字を書けば B は死ぬ。

ケース 2 がルール 1 に依存しているのが面白いところだ。「塗ったマスは接しない」がなければ、食い違いの隣に「両方で塗られていないマス」が保証されない。

実装では毎回この 2 ケースを全通り列挙して 1 個選ぶだけで、24 個の答えに対して 24 回とも成功する（テストが主張している）。

嘘つきだけの手掛かり集合は、いつ効くのか

存在は決着した。ではアルファベットを制限したらどうなるか。

嘘つき方言（exempt-only）: 手掛かりを「答えで塗られるマス」にしか置かない。全部が免除される、つまり全部が嘘だ。
正直方言（binding-only）: 手掛かりを「答えで塗られないマス」にしか置かない。全部が拘束される、つまり全部が真だ。

嘘つき方言のほうは、完全に答えが出る。

答えの塗りマス全部に言えない数字を書く。全部が白状するので、それらのマスは塗りで確定する。それ以外には何も言っていない。だからこの盤の答えは「意図した塗り集合を含む合法な塗り」全部だ。したがって:

• 答えにこれ以上 1 マスも足せない（合法性を保ったまま塗りマスを増やせない、つまり ⊆-極大）なら、含む合法な塗りは自分しかない。一意になる。
• 1 マスでも足せるなら、その大きい塗りも合法な答えで、しかも手掛かりは全部その大きい塗りでも塗られたマスの上に立っている——つまり大きい答えでも全部免除される。生き残る。しかもこれは「この手掛かり集合では駄目」ではなく、嘘つきだけで組んだどんな手掛かり集合でも駄目という主張になる（嘘つき手掛かりは定義上、答えの塗りマスの上にしか置けないので）。

嘘つきだけの手掛かり集合が存在する ⟺ 答えが ⊆-極大である。

両向きとも、540 個の答えで確かめた:

サイズ	密度	答え数	極大	うち一意	非極大	うち一意
5×5	0.18	60	0	0	60	0
5×5	0.24	60	7	7	53	0
5×5	詰められるだけ	60	60	60	0	0
6×6	0.18	60	0	0	60	0
6×6	0.24	60	10	10	50	0
6×6	詰められるだけ	60	60	60	0	0
7×7	0.18	60	0	0	60	0
7×7	0.24	60	4	4	56	0
7×7	詰められるだけ	60	60	60	0	0

極大 201 個は全部一意、非極大 339 個は 1 個も一意にならない。例外なし。

正直方言のほうが弱い

ここが「嘘つきは飾りではない」の裏づけになる。同じ貪欲な購入アルゴリズムで、置ける場所だけを変える:

疎な答え（塗り 20% 前後、この密度ではほぼ全部が非極大）

サイズ	盤数	極大率	自由選択の手掛かり数	嘘つきのみ成功率	正直のみ成功率	正直のみの手掛かり数
6×6	40	0.0%	11.9	0.0%	22.5%	14.1
8×8	40	0.0%	21.1	0.0%	10.0%	23.0

詰めた答え（もう 1 マスも入らない、つまり全部極大）

サイズ	盤数	極大率	自由選択	嘘つきのみ成功率	嘘つきのみ手掛かり数	正直のみ成功率	正直のみ手掛かり数
6×6	40	100%	10.4	100%	10.4	57.5%	11.1
8×8	30	100%	17.5	100%	18.3	16.7%	18.6

読み方はこうだ。

• 嘘つき方言は、効く場合には自由選択と同じ値段（6×6 で 10.4 対 10.4、8×8 で 18.3 対 17.5）。制限のペナルティがほぼゼロ。
• 正直方言は、そもそも成功しないことが多い。8×8 の詰めた答えでは 30 盤中 5 盤しか組めない。値段の問題ではなく、存在の問題だ。

前作までのシリーズでは「どちらの手掛かりも必ず存在する、あとは値段」という形が続いていた。ヤジサンカズサンでは崩れる。このパズルの表現力の主役は嘘つきのほうで、正直な手掛かりは不完全な方言だ。

最小手掛かり集合の 4 割は嘘つき

存在論から実測に戻る。一意性を買うための最小手掛かり集合を作って、そのうち何個が答えで免除されるか（＝嘘つきか）を数える:

サイズ	盤数	手掛かり総数	免除	免除率	言えない数字	その率	免除だが偶然真
6×6	40	478	217	45.4%	90	18.8%	20
8×8	40	842	366	43.5%	184	21.9%	26
10×10	30	931	379	40.7%	206	22.1%	25

4 割強が嘘つきで、そのうち半分弱は「そもそも言えない数字」＝ cap が 1 パス目で捕まえる自白だ。残りは「言えなくはないが、この答えでは違う」タイプ。そして 7〜9% は免除されているのに数字が偶然合っている（塗られたマスに立っているので誰も検算しないが、検算すれば通る）。

ここで最小性が効く。最小集合なのだから、どの手掛かりも 1 個抜けば一意性が壊れる。 実際に嘘つきだけを 1 個ずつ抜いてみると:

サイズ	抜いた嘘つき手掛かり	一意のまま	抜いた後の解数（中央値）	最大
6×6	217	0	8	200+
8×8	366	0	10	200+
10×10	378	0	11	200+

961 個の嘘つきを 1 個ずつ抜いて、一度も一意のままにならなかった。中央値で 8〜11 個の答えが湧く。嘘つきの手掛かりは、飾りどころか 1 個抜くだけで盤が崩壊する種類の情報を持っている。

盤面の側から見ても同じことで、答えの塗りマスは全体の 2 割程度しかないのに、手掛かりの 4 割がそこに乗っている——作者（ここでは敵対的な購入アルゴリズム）は、放っておくと嘘つきを過剰に選ぶ。

probe と一意性が完全に一致する

シリーズで毎回測っている 2 つの量がある。

1. 一意性に必要な手掛かり数（unique-min）
2. 探索なしで解けるようになるまでの手掛かり数（solve-min）

前作までは 1.08 倍くらいの階段があった。ヤジサンカズサンでは:

サイズ	盤数	unique-min	solve-min	比	unique-min 盤のグレード分布
6×6	40	11.9	11.9	1.00	probe:35 white:5
8×8	40	21.1	21.1	1.00	probe:32 white:8
10×10	30	31.0	31.0	1.00	probe:26 white:4

階段がない。 一意になった瞬間、probe（シングルトン整合性）は必ず探索なしで完答できる。

逆向きも掃いた。手掛かりの接頭辞を 718 通り作って、「probe が完答する」と「答えがちょうど 1 個」を突き合わせる:

サイズ	接頭辞	probe 完答	一意	一致率	probe だけ	一意だけ
6×6	358	40	40	100.0%	0	0
8×8	360	40	40	100.0%	0	0

両向きとも 0 件の食い違い。 これは前作（98.0% / 98.9%、一意なのに probe が止まる盤が 10 件）と対照的だ。理由は推測でしかないが、この puzzle の制約が「1 マスの真偽で局所的に矛盾が出る」形に寄っているからだろう——cap は 1 マス塗ると即座に自白を誘発するし、adj と white も 1 マスから伝播する。証明ではないので、そう観測されたという以上のことは言わない。

ablation: どの段を抜くと何が壊れるか

フルスタック（probe まで）から 1 段だけ外して、同じ盤に当てる:

サイズ	変種	不動点ビット	動いた盤	probe 回数	探索の仮定	予算超過
6×6	full	1440	0	436	0	0
6×6	−adj	127	40	3892	2,387,173	39
6×6	−cap	1421	1	2040	4	0
6×6	−ray	1339	6	2210	28	0
6×6	−white	1106	37	1652	4854	0
6×6	−probe	858	35	0	426	0
8×8	full	2560	0	800	0	0
8×8	−adj	244	40	7358	2,400,558	40
8×8	−cap	2492	2	3828	10	0
8×8	−ray	2324	8	4110	208	0
8×8	−white	2072	38	2512	23,674	0
8×8	−probe	1717	32	0	2244	0
10×10	full	3000	0	840	0	0
10×10	−adj	252	30	8476	1,800,166	30
10×10	−cap	2957	1	4642	2	0
10×10	−ray	2474	20	6510	790	0
10×10	−white	2661	25	2328	22,448	0
10×10	−probe	1928	26	0	7478	0

（−adj の行は探索予算 60,000 ノードをほぼ全盤で使い切っている（6×6 で 39/40、8×8 と 10×10 は全盤）ので、数字は「少なくともこれだけ」の意味しかない。）

ここにこの記事の主張と逆を向いている行がある。−cap が、ほとんど何も壊さない。 6×6 で不動点は 1440 → 1421、動いた盤は 40 盤中 1 盤、探索の仮定は 0 → 4。10×10 でも 1 盤だけ。

矛盾しているように見えるが、していない。ladder の表は各段を下から積んだときの値で、cap は下から 2 段目、そこでは唯一の情報源だ。ablation は上（probe 込み）から 1 段抜いたときの値で、シングルトン整合性は cap の推論を自力で再発見できる——「このマスが塗られていないと仮定 → 矢印が真でなければならない → 矛盾」は、まさに 1 マスのプローブだからだ。

つまり cap は安いショートカットであって、必要な公理ではない。実測でもそう出ていて、cap を抜くと probe の呼び出し回数が 6×6 で 436 → 2040、8×8 で 800 → 3828 と 4.7 倍に増える。同じ結論を、5 倍の値段で買い直している。

一方 adj を抜くと崩壊する。当然で、adj を抜くと cap の根拠（⌈L/2⌉ 上限）を支える「接しない」制約が伝播しなくなり、ray の DP も直線内の隣接を見なくなる。ヤジサンカズサンの推論は全部ルール 1 の上に乗っている。

第 2 解はどれくらい遠いか

このシリーズでは「第 2 解の大半は、探索ゼロの小さな証明書で説明できる」かどうかを毎回測っている。最小盤から手掛かりを 1 個抜いて曖昧にし、湧いた別解が答えと何マス違うかを数える:

サイズ	曖昧化した盤	平均で動いたマス	≤2	3-4	≥5	動いたマスのうち手掛かりマス
6×6	40	3.13	45.0%	37.5%	17.5%	40.8%
8×8	40	5.53	25.0%	22.5%	52.5%	38.9%
10×10	30	4.17	43.3%	23.3%	33.3%	31.2%

6×6 では 45% が「2 マス以下の入れ替え」で済むが、8×8 になると半分以上が 5 マス以上動く。盤が大きくなるほど、第 2 解は「局所的な差し替え」ではなくなる。

そして動いたマスの 3〜4 割が手掛かりマスそのものだ。これは嘘つきの仕組みから素直に説明がつく: 手掛かりマスの塗り／非塗りが入れ替わると、その手掛かりが免除されるかどうかが入れ替わる。別解は多くの場合、手掛かりの「有効／無効」を切り替えることで作られている。

外部台帳

自分のリポジトリの中だけで整合していても意味がないので、外の数に釘を打つ。ルール 2（連結）を切って手掛かりを 0 個にすると、残るのは「接しないように塗る」だけになり、これは格子グラフの独立集合の数そのものだ:

盤	行エンジン	マスエンジン	転送行列	OEIS
n×n, n=1..5	2, 7, 63, 1234, 55447	同	同	A006506（互いに利きあわない王子）
2×n, n=1..8	3, 7, 17, 41, 99, 239, 577, 1393	同	同	A001333（ペル・リュカ数）
3×n, n=1..7	5, 17, 63, 227, 827, 2999, 10897	同	同	A051736

3 つのエンジンは 1 行もコードを共有していない。bruteByRows は行ビットマスクを積むだけでマスを 1 個も見ない。bruteByCells は読み順にマスを走査してビットマスクを 1 個も作らない。independentSetCount は列挙せず転送行列で数えるので、列挙器が音を上げる 7×7（1,280,128,950）まで届く。

連結ルールを戻すと n×n の対角は 1, 5, 39, 562, 20297 になる。これは 2026-08 時点で OEIS に無い。無いこと自体は主張ではないが、テストには焼いてある。

1×n 帯には手計算の閉じた式がある。帯では「塗らないマスが連結」＝「塗らないマスが 1 本の連続区間」なので、塗れるのは両端だけ。両端は（n≥3 なら）互いに接しないから、答えは {}, {左}, {右}, {両端} の 4 通り（n=1 で 1、n=2 で 3）。列挙器 2 本とソルバーが全部一致する。

5 段の設計

段	内容
adj	塗ったマスの 4 近傍は塗らない
cap	直線が見せられない数字を書いた手掛かりは、自分のマスが塗られている
ray	手掛かりマスが「塗らない」と確定したら、その矢印は正直。直線上の DP で確定マスを読む
white	塗らないマスの連結性。到達不能マスと切断点の両方
probe	シングルトン整合性

ray の実装だけ少し書いておく。直線 r_1..r_L について、直線内の隣接だけを守りながら到達可能な合計値の集合をビットマスクで持つ DP を回す:

export function rayTotals(cells, rr, work, force = -1, forceVal = WHITE): number {
  let d0 = 1; // 直前が塗られていない場合の、到達可能な合計のビットマスク
  let d1 = 0; // 直前が塗られている場合
  for (let i = 0; i < rr.length; i++) {
    const s = i === force ? forceVal : cells[rr[i]];
    let n0 = 0, n1 = 0;
    if (s !== SHADED) n0 = d0 | d1;          // 塗らない
    if (s !== WHITE)  n1 = (d0 << 1) & 0x7fffffff; // 塗る（直前が塗られていないこと）
    d0 = n0; d1 = n1;
    if (d0 === 0 && d1 === 0) return 0;
  }
  return d0 | d1;
}

これが 3 通りに使い回される。

1. cap: 手掛かりマスを「塗らない」と仮定して回し、数字が到達可能集合に無ければ、その仮定が偽——マスは塗られている
2. ray: 手掛かりマスが「塗らない」と確定しているとき、直線上の各未確定マスを force で両側に固定して回し、片方しか数字に届かないなら確定
3. 直線の外の隣接は見ないので、これは緩和だ。潰しすぎることはなく、盤が埋まるほど鋭くなる

⌈L/2⌉ の上限は独立した定数として実装していない。空の直線に対して rayTotals を回せば、到達可能集合の最大値がちょうど ⌈L/2⌉ になる——テストは L=0..10 でそれを確かめている。上限は DP の1 パス目の系であって、別ルールではない。

生成

答え先行。ランダムな順にマスを見て、「接しない」かつ「塗らないマスが連結」を保てるなら塗る。棄却も再試行もない——置き終わった時点でもう合法な答えだ。密度パラメータを 1 にすると「もう 1 マスも入らない」まで詰める（1 パスでは足りないので不動点まで回す）。これがそのまま極大な答えになり、嘘つき定理の実験材料になる。

手掛かりは前述の 2 ケースをそのまま列挙して敵対的に買い、最後にシャッフルして 1 個ずつ落とす最小化をかける。だから出荷した盤の手掛かりは全部が必要（テストが 1 個ずつ抜いて確かめている）。

密度を振ると、値段が直感と逆を向く:

サイズ	密度	平均塗りマス	極大率	手掛かり 0 個での答え数	一意化に要る手掛かり
6×6	0.14	5.0	0.0%	1,646,096	12.8
6×6	0.18	6.0	0.0%	1,646,096	12.9
6×6	0.22	8.0	0.0%	1,646,096	11.8
6×6	詰めるだけ	10.3	100%	1,646,096	10.3

塗りマスが倍になっているのに、手掛かりは減る。 塗りマスが多いほど手掛かりを置ける「免除される席」が増え、免除される席に置いた手掛かりは数字が自由（＝別解を殺す自由度が最大）だからだ。手掛かりが自由に嘘をつけるマスが多い答えほど、安く一意にできる。

テスト

61 本。内訳としては、直線 DP を長さ 0..10 で総当たりと突き合わせるもの、ルール 4 の免除／拘束の非対称性（免除された手掛かりは値を全通りに書き換えても答えが壊れないが、拘束された手掛かりは 1 つでもずらすと壊れる）、単調性（手掛かりを足して答えが増えることはない・強い段が弱い段より決める量が少ないことはない）、伝播が答えと食い違うマスを 1 個も書かないこと、3 エンジンの解数・解集合の一致、外部台帳、嘘つき定理の両向き、出荷した盤が一意でグレードどおりで手掛かりに余りが無いこと。

構成

src/yajisan-kazusan.ts   モデル・5 段・伝播・探索・レフェリー
src/brute.ts             伝播器と 1 行も共有しない 2 エンジン＋転送行列
src/generate.ts          答え先行の生成と敵対的な手掛かり購入
tools/stats.mts          この記事の全ての表

---

デモ: https://sen.ltd/portfolio/yajisan-kazusan/
リポジトリ: https://github.com/sen-ltd/yajisan-kazusan