2015/01/17

8パズル,15パズルの不可能な配置と判定法

分野: 場合の数  レベル: 数学オリンピック

8パズル,15パズルにおいて,完成した形から2枚のパネルの場所を交換した状態からスタートしても完成させることはできない。

前提知識

8パズルの完成形
  • 8パズル,15パズルはパネルをスライドさせて目標の形(図の形)を作るゲームです。名前は知らないかもしれませんが,ほとんどの人が一度はやったことがあるゲームだと思います。
  • 8パズル,15パズルの解析には置換とそのパリティ(奇置換,偶置換)の知識を使います。知らなくても雰囲気は分かりますが,きちんと理解するためには置換の知識は必須です。→置換と偶置換・奇置換に関する基礎的なこと

状態に対応するベクトル

8パズルも15パズルも同じように扱うことができるので8パズルで解説します。

まず,8パズルの状態に対応する9次元ベクトル(9個の数字の並び)を考えます。左上から右下に向かって,どの数字が入っているのか順番に書き並べていきます(パネルがない「空き」の場所には9を入れます)。

8パズルの状態

例えば,図1の状態に対応するベクトルは,$(1,2,3,4,5,6,8,7,9)$ です。図2の状態に対応するベクトルは,$(2,1,3,4,9,6,7,8,5)$ です。

初期状態に対応するベクトルを $s$,完成した状態に対応するベクトルを $t=(1,2,3,4,5,6,7,8,9)$ と書くことにします。

不可能な配置の判定法と例

定理:$s$ に対応する状態からはじめたとき,
8パズルが完成できる $\iff$ $s$ を $t$ にする置換のパリティ(偶奇)と「空き」の最短距離の偶奇が等しい。

図1の例:完成不可能な配置

  • $s$ を $t$ にするには $7$ と $8$ を交換するだけでよい。互換一回で表せるので定理の左辺(置換のパリティ)は奇。
  • 「空き」の位置はスタートとゴールで同じ位置なので最短距離は $0$,すなわち偶。

図2の例:完成可能な配置

  • $s$ を $t$ にするには$(1,2),(5,9)$ を交換すればよい。互換二回で表せるので置換のパリティは偶。
  • 「空き」の位置はスタートとゴールで横に1,縦に1ズレている。最短距離は $2$,すなわち偶。

  • 15パズルでも同じ定理が成立します。より一般に $M\times N$ パズル$(M,\:N\geq 2)$ でも同じ定理が成立します。
  • この定理を認めれば冒頭の主張は直ちに導かれます。冒頭の主張では置換のパリティは奇で空きの最短距離は0だからです。

実際の判定法

実際に与えられた配置が可能かどうかは上記の定理を使って簡単に判定することができます。

・空きの最短距離はすぐに分かります。数えて下さい。

・初期状態 $s$ と完成状態 $t$ の置換のパリティを求めるためには,実際に $s$ を $t$ にする置換を互換たちで表してその偶奇を見ればOKです。これは置換をサイクル分解してもできますし,以下のように1から順番にそろえていってもOKです。

$s=(3,2,7,1,5,4,6,8,9)$ のとき,$s$ を $t$ にする置換のパリティを求めよ。
$s=(3,2,7,1,5,4,6,8,9)$ $(1,3)$ を交換
$\to (1,2,7,3,5,4,6,8,9)$ $(3,7)$ を交換
$\to (1,2,3,7,5,4,6,8,9)$ $(4,7)$ を交換
$\to (1,2,3,4,5,7,6,8,9)$ $(6,7)$ を交換
$\to (1,2,3,4,5,6,7,8,9)=t$
よって互換 $4$ 回で表せたので置換のパリティは偶。

不可能性の証明

定理の $\Rightarrow$ を証明します。
なお,$\Leftarrow$ については構成的に(偶奇が一致するときに8パズルを完成させるアルゴリズムを与える)証明できたつもりになっていますが,きちんと書くと煩雑なので省略します。

証明

初期状態 $s$ の $8$ パズルが完成できるとする。このとき,完成までにパネルを移動させた回数 $N$ の偶奇を二通りの方法で考える(二枚同時にスライドさせたら二回とカウント)。

・一回のスライドで「空き」スペースは必ず1マス移動するので,
$N$ の偶奇と「初期状態から終了状態の空きの最短距離」の偶奇は等しい。

・一回のスライドは互換に対応しているので $s$ から $t$ への置換は $N$ 回の互換で表せることになる。よって,
$N$ の偶奇と「 $s$ から $t$ への置換のパリティ」は等しい。

以上により定理の $\Rightarrow$ が証明できた。

今年のJJMO予選の最終問題は2×7パズルの問題でした。

Tag: 難しめの数学・雑学ネタまとめ

分野: 場合の数  レベル: 数学オリンピック