碁石ひろい — 答えを逆から読めてしまう盤は、パズルになれない

Posted at 2026-09-17

碁石ひろい（Goishi Hiroi）を 5 段のソルバー内蔵でブラウザに実装した。ルールは「どれかの石から出発してタテヨコに直進し、全部拾う」「進んだ先に石があったら必ず拾う（飛ばせない）」「石の上では曲がれるが、来た方向へは戻れない」——そして最後に「石は一度拾うと無くなる」。この一文が全部を決めている。旅人から見ると、自分が拾って空けたマスと、最初から石が無かったマスは同じ穴で、区別がつかない。だから残りの手数は（残っている石・現在地・到着方向）だけで決まり、どの石が昔そこにあったかには一切依らない。ここから 2 つ出てくる。(1) 1 枚の表が同じ格子の全配置を同時に値付けするので、4×5 の全 1,048,575 配置を 827 ms で数え切れる。(2) このパズルは時間対称ではない——前向きには 10 手前に拾った石の上を飛び越えられるが、逆から読むとその石はまだそこにある。つまり手順を逆から読んでも合法なのは、一度も飛び越えていないときちょうどその時で、したがって答えが 1 つしかない盤には必ず飛び越えが含まれていなければならない。数えた：全数え上げした 3×4 以下と、4×4 / 4×5 の各 12 万配置サンプルで、「答えが 1 つかつ逆から読める」盤は 0 件。同じ理由で、1 行盤は幅 12 まで、2 行盤は幅 10 まで、3×3 も、真のパズルがゼロ。3×4 が最小で、そこにちょうど 12 枚ある。石の数にも床があって、どの格子でも 2〜6 個の配置が一意になったことは一度も無い。全マス石の解数は 1×n が幅によらず 2、2×n が 2, 8, 20, 60, 172, 508, 1500, 4460, 13292 で a(n)=4a(n−1)−a(n−2)−6a(n−3)（13292 は漸化式で予測してから計算で確認）。OEIS には無い。梯子は line → reach → dead → probe → search の 5 段。全 57 テスト。ソルバー内蔵パズル第 68 弾。

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

ルール

碁石ひろいはニコリのパズル。実装前にニコリの公式ページを一次資料として読んだ。原文はこうだ。

いずれかの碁石(○)をスタートとして、タテヨコに線の上を進んで碁石をすべてひろいましょう。
進んだ先に碁石がない場合、そのまま直進します。
進んだ先に碁石があったら、その碁石をひろわなければなりません。また、その場所では進む方向を変えることができますが、いま来た方向へは戻れません。
碁石は１回ひろうとなくなるので、碁石があった場所をもう一度通っても、そこで方向転換はできません。

4 行しかない。しかも数字が 1 つも出てこない。手掛かりは石の配置そのもので、それ以外に盤に書いてあるものは何も無い。

この連作でこれまで実装してきたパズルは、ほぼ全部「盤に数字や記号を置き、それが盤面を絞る」という形をしていた。碁石ひろいにはそれが無い。置くものが無いということは、手掛かりの極小化という道具がまるごと使えないということでもある（後述）。

出荷している 6×6 盤の実例（o が石、右が答えの順番）:

  the board                 the order

   .  o  o  o  .  .         .  5  6  7  .  .
   .  .  .  .  .  .         .  .  .  .  .  .
   o  .  o  .  .  .        11  . 10  .  .  .
   o  o  o  .  o  .        12  4  3  .  2  .
   .  .  .  .  o  .         .  .  .  .  1  .
   o  .  o  o  .  o        13  .  9  8  . 14

9 → 10 の手を見てほしい。9 は最下行の 3 列目、10 は 3 行目の 3 列目。同じ列を上に進むが、その途中の 4 行目 3 列目には 3 の石があった。もう拾ってあるので、そこは穴だ。14 手目も同じで、最下行を右に進むとき 9 と 8 の上を飛び越えている。

拾ったマスと、最初から空のマス

ここが全部の出発点になる。ルール 4 行目「碁石は１回ひろうとなくなる」は、プレイ上は「そこで方向転換できない」という制限として書かれているが、状態空間の側から読むと違うことを言っている。

盤を進む旅人が「次の石はどれか」を決めるとき、見ているのは 残っている石 だけだ。拾って空になったマスと、最初から石が置かれていないマスは、どちらも通過するだけの穴で、旅人にはまったく区別がつかない。

したがって、ある局面から最後まで拾い切る方法の数は

f(残っている石の集合, 今いるマス, 到着した向き)

だけで決まる。どの石が昔そこにあったかは状態に入らない。

これは素朴に見えて、そう自明でもない。たとえば「拾い済みのマスは通れない」というルールだったら、盤の履歴が状態に入り込み、こうはならない。ニコリのルールは意図してか偶然か、履歴を完全に忘れさせる形になっている。

結果 1: 1 回のスイープで「全配置」が値付けされる

f が元の石配置に依存しないということは、同じ格子サイズのあらゆる石配置が同じ表を共有するということだ。マスク（残っている石のビット集合）を 0 から 2^cells−1 まで昇順に 1 回走らせれば、依存関係は必ずビットが 1 本減る方向にしかいかないので、素朴な数値順がそのまま位相順になる。

for (let mask = 1; mask < 1 << cells; mask++) {
  for (let pos = 0; pos < cells; pos++) {
    if (mask & (1 << pos)) continue;   // 今いるマスは拾った直後なので mask には無い
    let total = 0;
    for (let d = 0; d < 4; d++) {
      const t = firstIn(rays, mask, pos, d);   // その向きの最初の残り石
      if (t < 0) { hd[d] = 0; continue; }
      const v = f[(((mask ^ (1 << t)) * cells + t) * 5) + d + 1];
      hd[d] = v; total += v;
    }
    f[(mask * cells + pos) * 5] = cap(total);                 // 到着向き無し（出発）
    for (let d = 0; d < 4; d++)
      f[(mask * cells + pos) * 5 + d + 1] = cap(total - hd[(d + 2) % 4]);  // 逆走禁止
  }
}

「その向きの最初の残り石」はレイのビットマスクとの AND を取って最下位/最上位ビットを見るだけなので、内側は分岐の無い数語で済む。右・下は添字が増える向きなので m & -m、上・左は減る向きなので 31 - Math.clz32(m)。

表ができたあと、ある石配置の解数は Σ_{石 s} f(配置 \ {s}, s, 到着なし) という |石| 回のルックアップでしかない。つまり表を 1 回作れば、その格子の全部の盤が同時に値付けされる。

格子	石配置の総数	拾い切れる	答えが 1 つ	真のパズル（石 2 個以上）	スイープ
2x10	1,048,575	612,069 (58.4%)	20	0	761 ms
3x4	4,095	2,718 (66.4%)	24	12	1 ms
3x5	32,767	21,788 (66.5%)	275	260	10 ms
3x6	262,143	177,437 (67.7%)	3,582	3,564	99 ms
4x4	65,535	44,571 (68.0%)	416	400	25 ms
4x5	1,048,575	751,237 (71.6%)	10,316	10,296	738 ms

石 1 個の盤は自明に「答えが 1 つ」なので、最後の列ではそれを落としてある。その列がこの記事の主役で、上半分ではずっと 0 が並ぶ。

結果 2: このパズルは時間対称ではない

手順を逆から読んでみる。「来た方向へは戻れない」という条項は時間について対称なので、そこは壊れない。壊れるのは穴のほうだ。

前向きの手順では、10 手前に拾った石の上を飛び越えることができる。ところが逆から読むと、その石はまだ拾われていないので、そこに座って道を塞いでいる。逆に言えば:

手順を逆から読んでも合法になるのは、その手順が一度も「自分が空けたマス」の上を飛び越えていないとき、ちょうどその時。

これを「clean な手順」と呼ぶことにする。そしてここから、出題可能な盤が決まる。

答えが 1 つしかない盤の、その唯一の答えが clean だったとしたら、逆順が 2 つ目の答えになってしまう（石 2 個以上なら逆順は元と必ず違う）。したがって:

答えが 1 つの盤には、必ず「拾い済みのマスを飛び越える手」が含まれている。

これは仮定ではなく数えた。clean な手順の本数だけは元の配置に依存する（「昔そこに石があったか」を知る必要がある）ので、この表だけは盤ごとに作る。

格子	調べた配置	拾い切れる	答えが 1 つ	clean な答えを持つ	答えが全部 clean
2x4	247	175	0	175 (100.0%)	147 (84.0%)
2x5	1,013	681	0	681 (100.0%)	545 (80.0%)
2x6	4,083	2,629	0	2,629 (100.0%)	2,033 (77.3%)
3x3	502	343	0	339 (98.8%)	271 (79.0%)
3x4	4,083	2,706	12	2,616 (96.7%)	1,996 (73.8%)
4x4（12 万サンプル）	119,979	81,431	752	75,327 (92.5%)	58,753 (72.2%)
4x5（12 万サンプル）	120,000	86,196	1,165	76,618 (88.9%)	62,011 (71.9%)

一番右の列が全部 0。出荷している盤の側から見ても同じことで、72 枚全部が飛び越えを 1 つ以上含んでいる。編集判断でそうしたのではなく、含まないものは一意になれない。8×8 盤は平均 2.1 個、全 504 手のうち 10.1% が飛び越えだ。

だから小さい盤にはパズルが存在しない

飛び越えを作るには、一直線に石が 3 つ並んでいて、真ん中を先に拾ってから両端をつなぐ経路が要る。狭い盤では、それを作ったうえで他の全部の経路を殺す余地が無い。全数え上げが床を正確に出してくれる。

1 行盤: 幅 12 まで、真のパズルはゼロ。当然で、1 行の盤は「どちらかの端から反対の端へ」の 2 通りしか無く、その 2 つは互いに逆順だ。逆再生の議論の最小模型になっている
2 行盤: 幅 10 まで、ゼロ。全数え上げしたすべての 2 行盤で、拾い切れる配置は必ず clean な答えを持っていた（上の表の 100.0%）
3×3: ゼロ
3×4: ちょうど 12 枚。これがこのゲームの最小の盤

石の数にも床がある。測ったどの格子でも、石 2〜6 個の配置が一意になったことは一度も無い。最小のパズルは常に 7 個だ。

格子	最小パズルの石数	一番パズルが多い石数	その枚数	拾い切れる配置のうちの割合
3x4	7	12 マス中 7	12	1.83%
3x5	7	15 マス中 8	120	2.52%
3x6	7	18 マス中 9	1,128	3.38%
4x4	7	16 マス中 8	192	2.17%
4x5	7	20 マス中 10	3,464	2.45%

一番おいしい密度はだいたい半分で、格子を変えてもほとんど動かない。

全マスに石を置いた盤

盤を石で埋め尽くすと、解数がきれいな数列になる。

格子	解数	格子	解数
2x2	8	1x2	2
2x3	20	1x3	2
2x4	60	1x4	2
2x5	172	1x8	2
2x6	508	1x16	2
2x7	1,500	3x3	64
2x8	4,460	3x4	400
2x9	13,292	3x5	2,004
		3x6	11,936
		4x4	6,984

1×n が幅によらず 2 なのは前述のとおり。2×n は 8 項目まで出したところで線形漸化式を当てると

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

が出た。3 未知数を最初の 3 本で決めて残り 2 本で検算しているだけなので、この時点ではまだ疑わしい。そこで 2×9（18 マス、Float64Array で 189 MB）を実際に数えると 13,292。漸化式の予測値 4·4460 − 1500 − 6·508 = 13292 と一致した。テストは各項を漸化式からではなく素の探索から再導出するようにしてある。

どの数列も OEIS には無かった（2, 8, 20, 60, 172, 508, 1500, 4460 も、真のパズル数 12, 260, 3564 も、3×n の 64, 400, 2004 も）。

たった 8 語の条項を消してみる

「いま来た方向へは戻れません」——これは見た目、後始末のための細則にしか見えない。消して全数え上げをやり直すと、そうでもないことが分かる。

格子	拾い切れる（本来）	条項を消すと	答えが 1 つ（本来）	条項を消すと	両方で一意
3x4	2,718	3,259 (+19.9%)	24	232	12
3x5	21,788	27,274 (+25.2%)	275	1,351	15
3x6	177,437	227,637 (+28.3%)	3,582	6,522	18
4x4	44,571	54,427 (+22.1%)	416	2,928	112
4x5	751,237	917,043 (+22.1%)	10,316	29,980	1,444

制限を外したのだから解は増えるはずで、実際に拾い切れる盤は 2〜3 割増える。驚くのはそちらではなく、一意な盤も増えることだ。3×6 で 3,582 → 6,522。理由は、もともと解が 0 だった盤が解 1 を獲得するから。しかも「両方で一意」の列は小さい——4×5 で 10,316 のうち 1,444 しか生き残らない。

この条項は「答えを絞るためのもの」ではなく、どの盤が生きているかを決めるものだった。

生成器: 手掛かりが無いので、極小化も無い

このジャンルには置くものが無い。盤がそのまま石の配置で、石を 1 つ動かせば答えは全部書き換わる。他のパズルで使っている「答えから逆算して手掛かりを敷き詰め、削れるだけ削る」というループが丸ごと成立しない。

素朴にやるなら「石を撒いて解数を数える」だが、これは死ぬ。しかも盤のサイズではなく石の数で死ぬ。

格子	石	試した配置	答えが 1 つ	当たり率
6×6	8	1,438	28	1.95%
6×6	10	2,044	29	1.42%
6×6	12	2,541	16	0.63%
6×6	14	2,947	3	0.10%
6×6	16	3,237	2	0.06%
6×6	18	2,594	0	0.00%
8×8	14	2,232	10	0.45%
8×8	18	2,210	1	0.05%
8×8	22	1,882	0	0.00%

表を縦に読むと 6×6 では石 8 個の 1.95% が 16 個で 0.06% まで落ちる——石 8 個ぶんで 32 分の 1 だ。横に読むと、同じ 14 石なら 6×6 の 0.10% より 8×8 の 0.45% のほうが高い。つまり当たり率を殺しているのは盤の広さではなく石の数で、盤を広げるのはむしろ楽になる方向ですらある。出荷したい 8×8 / 22 石では 1,882 枚試して 0 件だった。

そこで答えのほうを先に作る。

石を 1 つずつ置きながら経路を伸ばす。ある手で未決定のマスの上を飛び越えたら、そのマスを banned（永久に空き）にする——そこに後から石を置いてしまうと、もう確定させた手を塞いでしまうからだ。すでに拾ったマスの上は自由に飛び越えてよく、そしてその飛び越えこそが「逆から読めない盤」に必要なものだった。

while (盤内) {
  if (used[i] >= 0) ghost = true;        // 拾い済み: 自由に飛べる
  else if (banned[i]) { /* 既に空き確定 */ }
  else {
    out.push({ to: i, dir: d, ban: ban.slice(), ghost });  // ここを次の石にできる
    if (ban.length >= maxBan) break;
    ban.push(i);                          // 通過するなら、ここは永久に空き
  }
  進む;
}

これで「少なくとも拾い切れる盤」が出る。あとは石を 1 つずつ動かす山登りで、解数（上限付きで数える）が増えない移動だけ受け入れて、1 本になるまで回す。

出荷盤	石	数え上げ回数	受け入れた移動	必要だった再スタート
6x6	14	中央値 17、最悪 141	中央値 6	中央値 1
8x8	22	中央値 43、最悪 137	中央値 11	中央値 1
10x10	30	中央値 99、最悪 177	中央値 38	中央値 1

棄却サンプリングが 1,882 枚で 0 件だった 8×8 / 22 石を、山登りは中央値 43 回の数え上げで通す。

梯子を 2 通りに値付ける

ヒントボタンは 5 段のうち 1 つを走らせる。

line — ルールそのもの。それ以上何も言わない
reach — 実際の手はすべて「行または列を共有する 2 つの石」を結ぶ。間に何が挟まっていても、それは先に拾えるかもしれないので、間を無視した行/列グラフは本物の手の緩和になる。残っている石はそのグラフで連結でなければならない
dead — その緩和グラフの形を見る。残りは 1 本のパスとして歩かれるのだから、次数 1 の石は 2 つまでしか許されない。しかも次の石は今いるマスと行か列を共有していなければならないので、それを満たさない低次数の石は「最後の 1 個」にしかなれず、そんな石は 1 つまで
probe — 各手を実際に打ってから、下の段にしゃべらせる
search — 探索そのもの

前向きに読むと、段の価値は「答えに沿った手のうち、その段だけで合法手が 1 本に絞れる割合」だ。

段	6x6	8x8	10x10
`line`	66.7%	59.9%	59.1%
`reach`	72.8%	65.7%	61.9%
`dead`	73.7%	67.5%	63.5%
`probe`	80.4%	71.6%	65.7%
`search`	100.0%	100.0%	100.0%

10×10 でも 6 割近くの手はルールだけで forced だ。数字を読む必要が無いパズルなので、「今どこに立っているか」が事実上すべての手掛かりになっている。逆に、上に積んでも 65.7% までしか行かない。残り 3 割強は本当に探索が要る。

同じ段を枝刈りとして測ると、印象がかなり変わる。

段	6x6 中央値	8x8 中央値	10x10 中央値	10x10 最悪
`line`	2,078	64,029.5	1,400,855	3,329,017
`reach`	326.5	7,443	78,181.5	229,632
`dead`	241.5	4,759	40,897.5	138,990
`probe`	169	3,445	29,568.5	101,477

証明としては 59.1% → 65.7% の 6.6 ポイントしか稼いでいない段が、枝刈りとしては 140 万ノードを 3 万ノードに落とす（47 分の 1）。reach の 1 段だけで 18 分の 1 だ。行/列の連結性という、パズルとしてはほとんど何も言っていないように見える条件が、探索木の大部分を消している。

出荷している盤

盤	枚数	石	手数	90° 曲がった	直進した	飛び越え	最長の 1 手	出発できる石
6x6	24	14	312	201 (69.8%)	87	中央値 1、最大 2	中央値 4.5、最大 5	1〜1
8x8	24	22	504	330 (68.8%)	150	中央値 2、最大 4	中央値 6、最大 7	1〜1
10x10	24	30	696	436 (64.9%)	236	中央値 3、最大 8	中央値 8、最大 9	1〜1

出発できる石はどの盤でもちょうど 1 つ。石 30 個の 10×10 盤でも、30 個のうち 29 個は「そこから始めたら必ず詰む」。最初の 1 手を当てるのがこのパズルの最初の関門で、ページのヒントで search 段を選ぶとそこだけ教えてくれるようにしてある。

実装メモ

状態は 5 スロット: f(mask, pos, dir) の dir は 0..3 に加えて「到着していない（出発）」の 1 枠が要る。(mask * cells + pos) * 5 + dir + 1 で引く。20 マスで 2^20 × 20 × 5 = 105 MB（Uint8Array）
上限付きの引き算が正しい理由: 各向きの寄与 h_d を CAP で切って合計 S を作り、到着向き dir の値を S − h_{opposite(dir)} で出している。切ってあるので一見危ないが、Σ_{i≠opp} min(h_i, CAP) は「真値が CAP 未満なら真値と一致、CAP 以上なら CAP 以上」を満たすので、最後にもう一度 min(·, CAP) すれば厳密に正しい
clean の数え上げだけは盤ごと: 「飛び越えたか」は元の配置を知らないと判定できないので、f の共有が効かない。firstIn(残り, pos, d) === firstIn(元配置, pos, d) を満たす手だけを許す DP を盤ごとに回している。だから逆再生の census は 3×4 までが全数、4×4 / 4×5 はサンプル、と正直に分けて出した
completable の予算切れは true を返す: 探索ノードの上限に当たったとき false を返すと「この手は死んでいる」と誤って言ってしまう。予算切れでは何も主張しないほうが安全なので true を返す
山登りのスコアは解数そのもの: 代理指標を使うと嘘をつくので、毎回上限付きで実際に数える。上限は 6×6 で 64、8×8 で 28、10×10 で 16。上限を上げるほど勾配は素直になるが、1 回の評価が高くつく
数値は全部 counts.json / stats.json から生成している。README とページの表は tools/notes.mts が書き出すので、手で転記した数字はゼロ。テストは出荷盤 72 枚それぞれについて「答えが合法」「答えがちょうど 1 つ」「飛び越えが 1 つ以上ある」「逆から読むと非合法」「出発できる石が 1 つ」を再導出し、census 側は素の探索と突き合わせる（全 57 テスト）

まとめ

碁石ひろいには数字が 1 つも無い。手掛かりは石の配置そのものだけで、置くものも削るものも無い。にもかかわらず、というよりだからこそ、出題可能性の条件が 1 行で書ける珍しいジャンルだった。

拾ったマスと空マスが区別できないので、状態は 3 つ組で閉じ、1 枚の表が全配置を同時に値付けする
同じ理由で時間対称性が壊れ、手順が逆から読めるのは「一度も飛び越えていないとき」ちょうどその時
したがって答えが 1 つの盤には必ず飛び越えがある——1 行盤にも 2 行盤にも 3×3 にもパズルが存在せず、3×4 にちょうど 12 枚あるのは、全部この 1 行の帰結

「一意である」という要求が、盤の幾何にここまで直接翻訳されるパズルは珍しい。

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

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up