ストストーンを解く — 「石を落とす」ルールは物理ではなく、列の数え上げと1本の不変量だった

ストストーンを、5 段のソルバー内蔵でブラウザに実装した。看板ルールは物理として書かれている——石を落とすと盤の下半分がちょうど埋まる——が、これは物理ではない。列ごとの数え上げと1 本の不変量であり、どちらも何ひとつ動かさずに判定できる。ソルバー内蔵パズル第 53 弾。

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

ルール

盤は H×W（H は偶数）で、領域に分割されている。

1. いくつかのマスを塗る。各領域の塗りマスはちょうど 1 つの連結な塊——石——を成し、どの領域にも 1 つある
2. 異なる領域の石どうしは接してはいけない
3. 領域内の数字は、その領域の石の大きさ
4. 石をまっすぐ下に落とす。石は剛体。落ち切った時、盤の下半分がちょうど埋まっていなければならない

ルール 4 がこのパズルの存在理由だ。そしてこの連作で実装してきた全ジャンルの中で、唯一「手続き」として書かれたルールでもある。何かをして、その結果を見る。他のペンシルパズルはすべて、目の前の盤面についての性質を述べる。だから最初の問いはこうなる: その手続きは本当に必要なのか。

必要ない。

数え上げの半分

落下はマスを縦に動かす。だから列に含まれる塗りマスの個数を変えられない。そして「下半分がちょうど埋まる」は、どの列も最終的に H/2 個の塗りマスを持つと言っている。したがって:

どの列も、最初から H/2 個の塗りマスを持つ。

まだ誰も計算していない最終形についての主張が、目の前の盤面に対するローカルな数え上げに化ける。コード 1 行で、これがソルバーの col 段のすべてだ。

残り

列の塗りマスを下から数える。下に空白が b 個あるマスは行 H−1−b に着地しなければならないから、H−1−b−r だけ動きたい。石は剛体なので、そのすべてのマスが同じ距離だけ動きたがる必要がある:

blankBelow(r, c) は 1 つの石のすべてのマスで等しく、その共通値がその石の落下距離そのものである。

これがルール 4 の全部で、シミュレーションは 1 行も入っていない。

export function packsByRank(h: number, w: number, cells: Int8Array): boolean {
  if (!columnsBalanced(h, w, cells)) return false;
  const below = new Int32Array(h * w);
  for (let c = 0; c < w; c++) {
    let seen = 0;
    for (let r = h - 1; r >= 0; r--) {
      below[r * w + c] = seen;
      if (cells[r * w + c] === BLACK) seen++;
    }
  }
  for (const comp of blackComponents(h, w, cells)) {
    let key = -1;
    for (const k of comp) {
      const v = Math.floor(k / w) + below[k];
      if (key === -1) key = v;
      else if (v !== key) return false;
    }
  }
  return true;
}

ここにはもう 1 つ隠れた問題がある。そもそも「石を落とす」はwell-defined ですらない。どの石から落とす？順番で結果は変わる？——変わらない。理由は書いておく価値がある: 同じ列を共有する 2 つの石は変位について d_i − d_j ≤ gap という制約を課し、差分制約系は成分ごとの max について閉じているので、最大解が一意に存在し、どんな貪欲スケジュールもそこに到達する。リポジトリは落下を2 通りのスケジュールで 2 回シミュレートし（全部を 1 行ずつ／1 個ずつ最後まで）、さらにシミュレートしない不変量と突き合わせる。テストが全探索できる盤サイズでは、3 者は完全に一致する。

目に見える系

同じ列にある 1 つの石の 2 マス（r < r'）に不変量を当てる。間にある塗りマスを B 個とすると blankBelow(r,c) = blankBelow(r',c) + (r' − r − 1 − B) で、不変量は B = r' − r − 1、つまり間の全部を強制する。ゆえに:

石は縦に穴を持たない。

これでルール 4 は 3 段の入れ子になる。

• count: どの列も H/2
• convex: それに加えて、石は縦に穴を持たない
• exact: 本物

3 つとも切り替え可能なルールセットとして出荷している。だから次の節が書ける。

数え上げは必要条件で、十分条件ではない

最小の反例は 4×3。どの列も 4 マス中 2 マス、どちらの石にも縦の穴がなく、それでもアーチは 1 行高いところで止まる——真ん中の脚が下のマスに乗ってしまうからだ。

# . #        . . .
# # #   ↓    # . #
. . .        # # #
. # .        . # .

領域も数字もない裸の盤で、H×W が許す塗り方を全部数えるとギャップに数字がつく。count は閉じた式 C(H, H/2)^W、他の 2 つは（バランスした盤だけを歩いて）列挙した。

盤	exact	convex	count	exact/count
2×n	2ⁿ	2ⁿ	2ⁿ	100.0%
4×2	28	36	36	77.8%
4×4	640	1,296	1,296	49.4%
4×10	7,618,204	60,466,176	60,466,176	12.6%
6×2	226	376	400	56.5%
6×4	31,820	133,760	160,000	19.9%
6×6	4,482,592	47,582,864	64,000,000	7.0%
8×2	1,940	4,248	4,900	39.6%
8×4	1,717,396	15,963,452	24,010,000	7.2%

この表の両端は証明でき、両方とも数値が一致する。2 行盤では 3 つの読みが一致する（穴をまたぐ石は列に 3 マス必要だが 2 マスしかない）ので exact = 2^W ちょうど。1 列盤はバランスしていれば必ず詰まるので exact = C(H, H/2)。縦の凸性も 4 行では空虚で（convex 列と count 列が 4×n の全行で一致している）、6 行から初めて効き始める。

4×n の数列は 6, 28, 134, 640, 3058, 14612, 69822, 333640, 1594282, 7618204。OEIS には無い。ただし

a(n) = 6·a(n−1) − 5·a(n−2) − 4·a(n−3)

を計算した全項で満たす——最初の 3 項からフィットして、続く 7 項で確認した。その幅の転送行列を書けば証明になるが、このリポジトリは持っていない。README にもそう書いてある。

盤を開けられない側が、外せない側だった

ソルバーは 5 段のはしごだ。col（ルール 4 の数え上げ半分）、clue（数字・領域 1 石・石は接しない・到達可能性）、fit（領域の石の描き方を全部並べて一致点を採る）、drop（不変量とその系）、probe（単点整合）。

出荷した 77 盤について、空盤から各段を累積で回すと:

サイズ	col	clue	fit	drop	probe
6×6	0.0%	37.9%	75.4%	78.5%	100.0%
8×8	0.0%	11.7%	26.2%	28.5%	100.0%

col は何も決めない。純粋な飽和ルールで、列を閉じることはできるが、開始時点ではどの列も閉じていない。盤を開けられない。ところが全段を回して書き込みを段に帰属させると:

サイズ	盤数	col	clue	fit	drop	probe
6×6	44	19.5%	37.8%	31.1%	5.5%	6.1%
8×8	33	14.6%	29.2%	22.1%	7.9%	26.2%

どこか他所から 1 マス与えれば、盤の 6 分の 1 を書く。そして全段から 1 段ずつ抜くと:

変種	確定率	探索なしで完答	仮定回数
全段	100.0%	77/77	0
− col	48.8%	1/77	350,027
− clue	98.6%	75/77	4
− fit	90.1%	67/77	47
− drop	76.1%	36/77	4,917

probe 無しでも順序は同じ（col 抜き 593,084、drop 抜き 14,306）。盤を開けられない側の半分は、外すと 71 倍高くつく。

今度はルール 4 を推論ではなくパズルのルールとして削ると、絵が裏返る。ここでは算術の半分のほうが「足りない」側だ。

サイズ	exact	convex	count	none
6×6	44/44	34/44	34/44	0/44
8×8	33/33	2/33	2/33	0/33

6×6 では、本物を数え上げに弱めると 44 盤中 10 盤が一意性を失う。しかも凸性を足し戻しても 1 盤も救えない——落ちるのは全く同じ 10 盤だ。8×8 では 33 盤中 31 盤がどちらでも一意性を失い、答えが 1 個だったところに中央値 37 個が立つ。出荷した 6×6 の領域割りの上では、数え上げだけだと 8,081 通り、本物だと 2,870 通り: 35.5%。

2 つの半分は「同じルールの小さい版が 2 つ」ではない。片方は演繹をほぼ全部やって曖昧性解消を何もせず、もう片方は演繹をほぼ何もせず曖昧性解消を全部やる。

手掛かりの言語が言えないこと

数字は領域に属し、その領域の石の大きさを言う。つまり手掛かりの言語はベクトル「領域 ↦ 大きさ」がすべてだ。存在しうる最強の手掛かり集合は「全領域に数字」であり、答えが一意化できるのはそのサイズベクトルを持つ合法盤が自分だけのとき、かつそのときに限る。これはよく失敗する。

盤	狙った石の大きさ	全数字で一意化	残る答えの中央値
6×6	2	57.1%	1
6×6	3	32.7%	2
6×6	4	20.6%	3
8×8	3	50.0%	1.5
8×8	4	33.3%	4

石が少なく大きいほど領域が少なく、ベクトルが短くなり、言えることが尽きる。この測定だけは出荷した盤からは取れない。 生成器は石を先に、領域割りを後に引き、全数字で一意化できるまで領域割りを引き直すからだ。残った盤で率を測るのは自分のフィルタを測ることになる。だからフィルタを切って別に測り、README でどちらがどちらか明記している。

一意化できる盤なら、必要な数字はごく少ない: 6×6 で 9.5 領域中 2.6 個、8×8 で 11.5 領域中 5.3 個。

生成は逆向きに走る

合法な局面はすべて「下半分をびっしり埋めたブロックを連結なピースに切り、持ち上げたもの」だ。これは不変量を右から左に読んだだけなので、生成器はルール 4 違反で答えを捨てる必要が一度もない。

1. 下 H/2 行を埋める——着地後の石の姿そのもの
2. そのブロックを連結なピースに切る
3. 各ピースを持ち上げる。列を共有する 2 ピースは順序を保つので、上のピースは下のピース以上に持ち上がる。制約は DAG を成し、たまに閉路が出たら「2 ピースが噛み合う必要がある」ということなので引き直す
4. 持ち上げた結果 2 ピースが接するなら却下——融合すると、落下距離が食い違うマスを持つ 1 個の石になってしまう
5. 石から外向きに領域を育て、数字を敵対的に買う

公式ではなく探索になるのは 4 だけだ。詰めたブロックは隙間なく solid なので、隣り合うピースは最初から必ず接していて、引き離せるのは持ち上げだけ。混み合った 8×8 ではランダムな持ち上げのほとんどが失敗する。だから 3 はバックトラックする。

答えの姿

サイズ	石の数	平均サイズ	平均落下距離	一度も動かない石
6×6	418	1.89	1.50	21.5%
8×8	381	2.77	2.03	17.1%

石の 5 分の 1 は最初から着地済みだ。これはタダの情報で、どこかの列で下に空白があれば落下距離は正、床に接していればそのすべてのマスの下が全部塗りだと決まる。

突き合わせ

コードを共有しない 3 つのエンジンが一致しなければならない: 伝播つき探索、盤を整数と見て全部試す列挙器、各領域の石をその領域の連結部分集合から選ぶ列挙器。ランダムな 4×4 領域割り 60 通りで、答え 503 個すべてが一致し、ルール 4 の 4 設定すべてで一致する。

probe は健全だが完全ではない。手掛かり接頭辞 876 通りで、答えが 2 つ以上ある盤を「完答した」と言ったことは一度もない。逆に、答えが 1 つなのに探索が要った盤が 3 回。この連作でずっとそうであるように、ギャップは片方向にしか開かない。

突き合わせが捕まえたバグ

面白い失敗はパズル側ではなかった。落下の2 つ目のシミュレータ——1 個の石を最後まで落としてから次に移るほう——にあった。座標系を 2 つ混ぜていた: 石のマス集合は落下に合わせてその場で更新しているのに、衝突判定はその上にさらに累積落下量を足していた。石が 1 個の盤では見えない。石が別の石の上に乗ったときだけずれる——このパズルが丸ごとそれについてのパズルであるところの、まさにその場合だけ。

パズル側のテストでは絶対に捕まらない。パズル側はこの関数を呼ばないからだ。捕まえたのは「2 つのスケジュールが同じ不動点に到達する」というプロパティテストで、これは「落下は順序に依存しない」がこのリポジトリの主張だから書いたものだった。主張には、落ちると思っていなくてもテストを書く価値がある。

動かす

npm install
npm run dev      # ローカルでデモ
npm test         # 70 テスト
npm run build

MIT。