15パズルには絶対に解けない並びがある

15パズルでは、正しい完成形から14と15だけを入れ替えた並びは解けません。駒を取り外さず、空白へ上下左右に滑らせるという通常の操作だけでは、何万回動かしても到達できないのです。判定の鍵は、数字の逆転数と空白の行番号の偶奇にあります。

ここでは4行4列の盤面に、1から15を左上から横に順番に置き、右下を空白とする完成形を考えます。完成形が違う場合には、以下の条件をそのまま使わず、目標の盤面との偶奇を比較して下さい。

盤面を左上から右へ、次の行も左から右へと読み、空白を飛ばして15個の数字の列を作ります。前にある数が後ろの数より大きい組を一つずつ数えたものが、逆転数Iです。「隣同士が逆になっている箇所」だけを数えるのではありません。

例えば3、1、2なら、逆転は（3,1）と（3,2）の2組です。完成形1、2、…、15では0組。上の盤面では（15,14）だけなので1組です。数字の差の大きさも関係なく、一つの組は1として数えます。

空白が下から何行目にあるかをrとします。最下段を1、その上を2、3、4と数えます。通常の完成形へ到達できるための必要十分条件は、次の通りです。

$$I+r\equiv1\pmod2$$

つまり、I＋rが奇数なら解けて、偶数なら解けません。完成形はI＝0、r＝1なので奇数。14と15だけを交換した盤面ではI＝1、r＝1なので偶数となり、解けないと分かります。資料によって「上から0、1、2、3」と行を数える表記もあります。行番号の起点を混ぜないことが大切です。

空白と横隣の駒を交換しても、空白を除いた数字の列は同じ順序です。逆転数Iも空白の行rも変わりません。縦隣と交換した場合は、動かした数字が、列として読んだときに他の3個の数字をまたぎます。各組の大小の前後が反転するため、逆転数の偶奇が変わります。

同時に、空白の行も1行だけ変わるのでrの偶奇も変わります。二つが一緒に反転する結果、I＋rの偶奇は保存されます。このように、操作を何度行っても変わらない量を不変量といいます。違う偶奇の盤面を結ぶ手順は、最初から存在しません。

例えば完成形で12を下へ動かすと、空白は下から2行目へ移ります。数字の列の末尾は13、14、15、12となり、逆転数は3。I＋r＝3＋2＝5で、やはり奇数です。「解ける盤面は逆転数が偶数」とだけ覚えると、この1手で作れる盤面を誤判定してしまいます。

不変量の説明だけで直接示せるのは「偶奇が違えば不可能」という向きです。通常の長方形スライドパズルの到達可能性の結果を用いると、4×4では条件を満たす盤面は全て解けることも分かります。したがって、空白も含めた16個の場所の全16!通りのうち、完成形へ到達できるのは半分です。

ただし、解けると判定できても、最短手順が分かるわけではありません。遠くの駒を戻すために一度そろえた列を崩す必要もあります。問題を作るなら、完成形から合法な操作で十分に混ぜれば、必ず解ける盤面ができます。駒をばらして無作為に置き直す方法では、半分が解けない問題になる点に注意しましょう。

3×3の8パズルでは縦移動でまたぐ数字が2個になるため、逆転数そのものの偶奇が保存され、通常の完成形へ解ける条件はIが偶数となります。盤面の幅が偶数か奇数かで判定式が変わるのも、同じ数え方から理解できます。

資料確認日：2026年10月2日。本文の数値例・模式図は、特記したものを除き本記事の説明用に作成しています。