15パズルに解けない配置がある理由｜14と15の入れ替えと見分け方

15パズルには、何手動かしても完成しない配置があります。完成形の14と15だけを入れ替えた並びがその一例です。ただし、途中で手が止まったことだけでは「解けない配置」とは判断できません。数字の並びと空きマスの位置を、図で確かめてみましょう。

14と15だけが逆でも、完成できない

ここでは、4×4の盤面を左上から1〜15の順にそろえ、右下を空きマスにするルールを考えます。動かせるのは空きマスの上下左右に隣り合う1枚だけ。タイルを持ち上げたり、2枚を直接交換したりはできません。

図1：目標の完成形。最後の行は13・14・15・空き。

図2：14と15だけを交換した配置。通常のスライド操作では図1に戻せません。

見た目ではあと少しですが、図2は手順を工夫しても完成できません。反対に、完成形から合法なスライドだけで崩した盤面は、動かした順を逆にたどれば必ず戻せます。「難しくて解けない」と「ルール上、完成に到達できない」は別のことです。

図は説明用に用意した配置です。図2の解けない配置を、通常のプレイ問題として出題しているわけではありません。

最初に、空きを飛ばして左上から右へ、上の行から下の行へ数字を読みます。その列で大きい数字が小さい数字より前にある組を数えます。これを「逆転の数」と呼びます。隣同士だけでなく、離れた組も数えます。

たとえば「3・1・2」なら、逆転は「3と1」「3と2」の2組です。図2では1〜13は順番どおりなので、逆転は「15と14」の1組だけになります。

次に、空きマスが下から何行目かを数えます。一番下は1行目、その上は2行目です。この2つの数を足します。

4×4で右下を空きにする完成形の場合、合計が奇数なら解ける配置、偶数なら解けない配置です。

空きの位置を数え忘れないことが大切です。3×3にはこの足し算の判定を使いません。3×3で右下を空きにする場合は、逆転の数だけが偶数なら解けます。

逆転の数そのものは変わりますが、4×4では「逆転の数＋空きの行」の偶数・奇数が変わりません。横と縦の動きを分けると分かります。

横へ1マス動かすとき：空きを飛ばして読んだ数字の順序は変わりません。空きの行も同じなので、合計の偶奇は変わりません。

縦へ1マス動かすとき：動かす数字は、読み順でほかの3個の数字を追い越します。逆転の数は奇数分増減し、偶奇が切り替わります。同時に空きの行も1つ変わるため、こちらの偶奇も切り替わります。2つを足した結果の偶奇は同じままです。

完成形の合計は奇数です。偶数の配置から何度スライドしても偶数のままなので、完成形には到達できません。このように、操作しても変わらない性質が「不変量」です。奇数側の配置がすべて完成形へ到達できるという逆向きの結論も成り立ちます（参考資料の定理1.4）。

図3：完成形から12を下へ動かした配置。逆転は13と12・14と12・15と12の3組、空きは下から2行目。3＋2＝5で奇数です。

図3は逆転が3組あっても解けます。12を上へ戻せば完成です。「逆転が奇数だから解けない」とだけ覚えると、4×4では間違ってしまいます。

図4：最後の行が13・空き・14・15の配置。2つの数を確認してみましょう。

答えと動かし方を見る

解けます。空きを除いた数字は1〜15の順なので、逆転は0組。空きは下から1行目で、合計は1です。14を左へ、続いて15を左へ滑らせると完成します。

パズル図鑑の15パズルは、完成形から合法な操作で崩し、戻せることを検証した問題です。行き詰まったときは15パズルの解き方で、行末の2枚や最後の2行の扱いを確認できます。

下の「ふつう」「むずかしい」は4×4、「やさしい」は同じスライド操作の3×3です。表示される解答手順は一例で、最短手順とは限りません。

石川勝巳「不変量で見るトポロジー」（京都大学数理解析研究所・2022年度数学入門公開講座）、1.2節「15パズル」、3〜4ページ。不変量による不可能性と、到達可能性の判定を参照しました。本記事の図・練習は自作し、配置と手順を検証しています。