【論文601】15 パズルの局面の半分は、どう動かしても届かない

要旨

15 パズルは、$4\times4$ の盤に $1$ から $15$ の駒と一つの空所を置き、空所に隣の駒を滑らせて並べ直す遊びである。どんな並べ方からでも完成形に戻せるか、を数で確かめる。新しい定理も法則も主張しない。

第一に、小さい盤で探索すると、届くのはちょうど半分である。$2\times2$ で $24$ 局面のうち $12$、$2\times3$ で $720$ のうち $360$、$3\times3$ で $362880$ のうち $181440$ である。$3\times3$ の最長は $31$ 手（$2$ 局面）、平均は $\mathbf{21.972399}$ 手である（第2節）。

第二に、届く側を見分ける量が一つある。駒の並びの偶奇（完成形から何回の入れ替えで作れるかの偶奇）と、空所が完成位置から何マス離れているかの偶奇の和である。$3\times3$ の全 $362880$ 局面をこの量で分けると、$0$ の側の $181440$ 局面が、探索で届いた局面とちょうど一致する（第3節）。

第三に、15 パズルでも半分である。全局面 $16!=20922789888000$ のうち、届くのは $10461394944000$ である。$14$ と $15$ だけを入れ替えた局面は量が $1$ で、届かない側にある。$200000$ 手の乱歩でも、量は $0$ のままだった（第4節）。

第四に、これが本稿の芯である。量が変わらないのは、盤が二色に塗り分けられるからである。空所は一手ごとに隣のマス、つまり反対の色へ移り、駒の並びは一回の入れ替えだけ変わる。二つの偶奇が必ず一緒に反転する（第5節）。

第五に、分離子は、長さが奇数の輪があるかである。左右の端をつないで $3$ 列を輪にすると、長さ $3$ の輪ができて二色に塗れなくなり、$2\times3$ は $720$ 局面すべて、$3\times3$ は $362880$ 局面すべてに届く。$4$ 列を輪にしても長さ $4$ の輪で二色に塗れるので、$2\times4$ は $40320$ のうち $20160$ にとどまる（第5節）。

第六に、検算で、私は一度予想を外した。端をつないだ $4\times4$ では距離の偶奇の数え方が保存されなくなると予想したが、保存された。端を越える一手は空所の距離を $3$ 変え、$3$ は奇数だからである。距離の偶奇と色の偶奇は同じ量で、全 $362880$ 局面で一致した（第5節）。

キーワード：15 パズル、置換の偶奇、不変量、到達可能性、二色の塗り分け。

射程（何を示さないか）

新しい定理も法則も主張しない。15 パズルの半分が届かないこと（ジョンソンとストーリー、$1879$）、グラフの上の同じ種類のパズルの一般の定理（ウィルソン、$1974$）、$3\times3$ の最長が $31$ 手であること（ライネフェルト、$1993$）は、いずれも既知である。$16!$ 局面は探索しない。$4\times4$ は量と乱歩で確かめるだけで、残りの半分に全部届くことは小さい盤の探索と既知の結果に拠る。最短手数の探し方を扱わない。最長と平均は、幅優先探索で全局面を数えた値である。ウィルソンの定理を証明しない。端をつないだ盤は、分離子を数で確かめるための例である。既刊との関係：論文247 は「偶数と奇数で分かれる」を八つに数え、ガンマ関数の半整数・時間反転・グリーン関数の台・行列式の符号などを並べた。本稿の偶奇は駒の並びの偶奇（置換行列の行列式の符号）で、それが効くかどうかは盤の形で決まる。加えたのは、小さい盤で探索と偶奇の数え方を局面ごとに突き合わせたこと、分離子を「長さが奇数の輪があるか」に置き、端をつないだ盤で数で確かめたこと、距離の偶奇と色の偶奇が同じ量であることを全局面で確かめたことである。

1. 記法と問い

設定：$r\times c$ の盤に $1$ から $rc-1$ の駒と空所を置く。完成形は、駒が左上から番号順に並び、空所が右下にある局面である。一手は、空所と、上下左右に隣り合う駒を入れ替えることである。

見張る量：局面 $s$ について、完成形から $s$ を作る置換（空所も一つの駒と見る）の偶奇を $\mathrm{par}(s)$、空所の位置 $(r_0,c_0)$ と完成位置 $(r_*,c_*)$ の距離を $d(s)=|r_0-r_*|+|c_0-c_*|$ とし、

$$I(s)=\bigl(\mathrm{par}(s)+d(s)\bigr)\bmod 2$$

と置く。完成形では $I=0$ である。

問い：完成形から届く局面はどれだけあり、それを $I$ で見分けられるか。見分けられるのはなぜか。

2. 探索で数える

計算 2.1：完成形から幅優先探索で、届く局面を全部数えた。

観察 2.2　三つの盤で、届くのはちょうど半分である。割合はどれも $0.500000$ で、$3\times3$ の最長 $31$ 手・$2$ 局面は、ライネフェルトが全局面を解いて出した値と一致する。残りの半分からは、どう動かしても完成形に戻れない。

3. 偶奇で数える

計算 3.1：探索とは独立に、$3\times3$ の全 $362880$ 局面の $I$ を計算した。$I=0$ の局面は $181440$、$I=1$ の局面も $181440$ だった。

観察 3.2　$I=0$ の局面の集合は、探索で届いた集合とちょうど一致した。数が同じなだけでなく、局面ごとに一致する。$2\times3$ でも一致した。届くかどうかは、探索しなくても $I$ だけで分かる。

観察 3.3　$I$ が変わらない理由。一手で空所と駒を入れ替えると、置換は一回の入れ替えだけ変わるので $\mathrm{par}$ が反転する。同時に空所は隣へ一マス動くので、$d$ は $1$ 増えるか減るかして偶奇が反転する。二つが必ず一緒に反転するので、和の偶奇は変わらない。だから $I=1$ の局面には届かず、届くのは多くとも半分である。

4. 15 パズル

計算 4.1：$4\times4$ の全局面は $16!=20922789888000$ で、探索はできない。$I$ で分けると、届く側は多くとも $10461394944000$ である。$14$ と $15$ だけを入れ替えた局面（ロイドが懸賞をかけた局面として知られる）は $I=1$ だった。完成形から $200000$ 手の乱歩をさせ、$1000$ 手ごとに $200$ 回 $I$ を確かめると、一度も $1$ にならなかった。

観察 4.2　15 パズルでも、見張る量は同じ働きをする。$14$ と $15$ の入れ替えは、どれだけ手をかけても作れない。$I=0$ の側に全部届くことは、ジョンソンとストーリーが示している。本稿は小さい盤の探索でそれを確かめただけである。

5. 分離子

観察 5.1　これが本稿の芯である。$I$ が効くのは、盤が二色に塗り分けられるからである。市松模様に塗ると、隣り合うマスは必ず違う色になる。空所は一手ごとに反対の色へ移り、駒の並びは一回の入れ替えだけ変わる。$d$ の偶奇は、空所が完成位置と同じ色にいるかどうかにほかならない。

計算 5.2：左右の端をつないで、各行を輪にした盤で探索した。

観察 5.3　分離子は、長さが奇数の輪があるかである。$3$ 列をつなぐと長さ $3$ の輪ができ、市松模様に塗れなくなる。そのとき全局面に届く。$4$ 列をつないでも輪の長さは $4$ で塗れるので、半分にとどまる。端を越える一手は、空所の距離 $d$ を列の数より $1$ 少ない数だけ変える。$3$ 列では $2$（偶数）で、置換の反転と打ち消し合わない。$4$ 列では $3$（奇数）で、打ち消し合う。

観察 5.4　検算で、私は一度予想を外した。端をつないだ $4\times4$ では「距離の偶奇で数える $I$ は保存されなくなり、色で数え直さなければならない」と予想して、その検査を書いた。実測では、距離で数えた $I$ も一度も $1$ にならなかった。端を越える一手が距離を $3$ 変えることを見落としていた。距離の偶奇と色の偶奇は、$|x|$ と $x$ の偶奇が同じなので同じ量であり、$3\times3$ の全 $362880$ 局面で一致した。検査は実測に合わせて直した。

観察 5.5　論文247 と並べる。247 は「偶数と奇数で分かれる」を八つに数えた。本稿の偶奇は駒の並びの偶奇で、置換行列の行列式の符号である。ただしそれが届く・届かないを分けるかどうかは、偶奇そのものではなく、盤に長さが奇数の輪があるかで決まる。

観察 5.6　言わないこと。$16!$ 局面を探索していない。ウィルソンの一般の定理を証明していない。最短手数の探し方は扱わない。示したのは、小さい盤で二つの道筋が局面ごとに一致すること、そして分離子を動かすと届く局面の数が変わることである。

6. 点呼と結び

1. $3\times3$ で $362880$ 局面のうち $181440$ に届く（計算 2.1）：ちょうど半分。
2. 最長 $31$ 手・$2$ 局面、平均 $\mathbf{21.972399}$ 手（計算 2.1）：既知の値と一致。
3. $I=0$ の集合が探索の集合と局面ごとに一致（観察 3.2）：二つの道筋。
4. 一手で二つの偶奇が一緒に反転する（観察 3.3）：和が変わらない。
5. $16!$ のうち届くのは $10461394944000$（計算 4.1）：15 パズルでも半分。
6. $14$ と $15$ の入れ替えは $I=1$（計算 4.1）：作れない。
7. 盤が二色に塗れるから効く（観察 5.1）：本稿の芯。
8. $3$ 列をつなぐと全局面に届き、$4$ 列では半分（計算 5.2）：分離子は奇数の輪。
9. 端を越える一手は距離を $2$ または $3$ 変える（観察 5.3）：偶数なら破れ、奇数なら保たれる。
10. 距離の偶奇と色の偶奇は同じ量（観察 5.4）：外した予想から出た。

結び：15 パズルは、どんな並べ方からでも完成形に戻せるように見える。実際に戻せるのは、ちょうど半分である。$3\times3$ の盤では幅優先探索で $362880$ 局面のうち $181440$ に届き、駒の並びの偶奇と空所の距離の偶奇の和で分けた $181440$ 局面と、局面ごとに一致した。$4\times4$ では $16!$ のうち $10461394944000$ である。この量が変わらないのは、盤が二色に塗り分けられるからである。空所は一手ごとに反対の色へ移り、駒の並びは一回の入れ替えだけ変わるので、二つの偶奇が必ず一緒に反転する。分離子は、長さが奇数の輪があるかである。端をつないで長さ $3$ の輪を作ると $2\times3$ は $720$、$3\times3$ は $362880$ の全局面に届き、長さ $4$ の輪では $2\times4$ は $40320$ のうち $20160$ にとどまった。既刊との位置、論文247 が数えた偶奇の分かれに、盤の形で効くかどうかが決まる偶奇を一つ並べる。正直に言えば、$16!$ 局面は探索しておらず、残りの半分に全部届くことは小さい盤と既知の結果に拠る。検算では一度、端をつないだ $4\times4$ について予想を外し、実測に合わせて直した。

参考文献

1. Johnson, W. W., & Story, W. E. (1879). Notes on the “15” puzzle. American Journal of Mathematics.
2. Reinefeld, A. (1993). Complete solution of the eight-puzzle and the benefit of node ordering in IDA*. Proceedings of the International Joint Conference on Artificial Intelligence.
3. Wilson, R. M. (1974). Graph puzzles, homotopy, and the alternating group. Journal of Combinatorial Theory, Series B.
4. 山岸勇輝 (2026). 『「偶数と奇数で分かれる」は、一つの現象ではない』[論文247]. Zenodo. 10.5281/zenodo.22159832

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「15 パズルの局面の半分は、どう動かしても届かない」［論文601］. Zenodo.
DOI: 10.5281/zenodo.22805752

@misc{yamagishi2026yoi601,
  author = {Yamagishi, Yuuki},
  title = {Half of the Fifteen Puzzle's Positions Can Never Be Reached},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/601},
  doi = {10.5281/zenodo.22805752},
  note = {Preprint, edition 1}
}