why-is-the-15-puzzle-unsolvable

15パズルが解けない理由

「15パズル」、別名「15デジタル問題」は、解けないのではなく、特定の初期状態では目標状態に到達できないということです。

ゲームの説明

「15パズル」は、スライドゲームで、ゲームボードは4×4のグリッドで、15のスライダー（1から15までの数字）と空いたスペースがあります。プレイヤーの目標は、スライダーを左から右へ、上から下への順序で移動し、1から15までの順序で並べ、右下のコーナーにスペースを配置することです。

解けないケース

初期状態の逆順ペアの数が奇数の場合に限り、目標状態に到達するために合法的に移動することはできません.逆順ペアとは、系列の中の2つの数の組で、前後の位置が大きさに逆の順序になっている場合（つまり、前方の数字が後ろの数字より大きい）を指します。例えば、系列 2, 4, 3, 1 では、逆順ペアは (2, 1), (4, 3), (4, 1), (3, 1) の4つです。

証明

ボード上のスライダーの移動は、これらのスライダーの配置の変換とみなすことができます。スライダーを移動するたびに、スペースは隣接するスライダーと交換されます。この交換操作により、配置の逆順のペアの数の奇偶性が変化します。目標状態の逆順ペアの数は0で、偶数です。初期状態の逆順ペアの数が奇数の場合、何度移動してもその奇偶性は偶数に変わりません。したがって、目標状態に到達することはできません。

Puzzles ballもプレイしてみたい方は、無料で楽しく簡単に遊べます。