YOI 601：15 パズルの局面の半分は、どう動かしても届かない

論文601 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/601 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（DOI：10.5281/zenodo.22805752）。

本文はサイトの記事でも読めます：【論文601】15 パズルの局面の半分は、どう動かしても届かない

@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}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969434・969435・969440・969461 に記録されました（2026年10月01日 18:16（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

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 パズル、置換の偶奇、不変量、到達可能性、二色の塗り分け

Abstract

The fifteen puzzle places tiles $1$ to $15$ and one blank on a $4\times4$ board; a tile next to the blank is slid into it to rearrange them.Whether every arrangement can be brought back to the solved position is checked here in numbers.No new theorem or law is claimed.

First, searching small boards, exactly half the positions are reachable、$12$ of $24$ on $2\times2$, $360$ of $720$ on $2\times3$, and $181440$ of $362880$ on $3\times3$. On $3\times3$ the longest distance is $31$ moves ($2$ positions) and the mean is $\mathbf{21.972399}$ moves (Section 2).

Second, one quantity tells the reachable side、the sum of the parity of the tiles’ arrangement (how many swaps make it from the solved position) and the parity of the blank’s distance from its home. Splitting all $362880$ positions of $3\times3$ by this quantity, the $181440$ with value $0$ coincide exactly with those reached by search (Section 3).

Third, the fifteen puzzle is also half、of all $16!=20922789888000$ positions, $10461394944000$ are reachable. The position with only $14$ and $15$ swapped has value $1$ and is on the unreachable side. In a random walk of $200000$ moves, the value stayed $0$ (Section 4).

Fourth, and this is the core.The quantity never changes because the board can be coloured in two colours、each move sends the blank to a neighbouring square, that is, to the other colour, and changes the arrangement by exactly one swap. The two parities always flip together (Section 5).

Fifth, the separator is whether there is a cycle of odd length、joining the left and right edges so that $3$ columns form a cycle creates a cycle of length $3$, the board can no longer be coloured in two colours, and $2\times3$ reaches all $720$ positions and $3\times3$ all $362880$. Joining $4$ columns gives a cycle of length $4$, still two-colourable, and $2\times4$ stays at $20160$ of $40320$ (Section 5).

Sixth, in checking, I once predicted wrongly、I expected that on a $4\times4$ board with edges joined the count by distance parity would stop being preserved, but it was preserved: a move across the edge changes the blank’s distance by $3$, which is odd. Distance parity and colour parity are the same quantity, agreeing on all $362880$ positions (Section 5).

Keywords: 15 puzzle, parity of permutations, invariant, reachability, two-colouring

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/601/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/601 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ