1. 高校数学の美しい物語
  2. 8パズル,15パズルの不可能な配置と判定法

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

更新日時 2021/03/07

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)(1,2,3,4,5,6,8,7,9) です。図2の状態に対応するベクトルは,(2,1,3,4,9,6,7,8,5)(2,1,3,4,9,6,7,8,5) です。

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

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

定理

ss に対応する状態からはじめたとき,

8パズルが完成できる     \iffsstt にする置換のパリティ(偶奇)と「空き」の最短距離の偶奇が等しい。

例えば,上記の図1は「完成不可能な配置」です。実際,

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

一方,上記の図2は「完成可能な配置」です。実際,

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

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

実際の判定法

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

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

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

s=(3,2,7,1,5,4,6,8,9)s=(3,2,7,1,5,4,6,8,9) のとき,sstt にする置換のパリティを求めよ。

s=(3,2,7,1,5,4,6,8,9)s=(3,2,7,1,5,4,6,8,9)

(1,3)(1,3) を交換

(1,2,7,3,5,4,6,8,9)\to (1,2,7,3,5,4,6,8,9)

(3,7)(3,7) を交換

(1,2,3,7,5,4,6,8,9)\to (1,2,3,7,5,4,6,8,9)

(4,7)(4,7) を交換

(1,2,3,4,5,7,6,8,9)\to (1,2,3,4,5,7,6,8,9)

(6,7)(6,7) を交換

(1,2,3,4,5,6,7,8,9)=t\to (1,2,3,4,5,6,7,8,9)=t

よって互換 44 回で表せたので置換のパリティは偶。

不可能性の証明

定理の \Rightarrow を証明します。

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

証明

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

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

  • 1回のスライドは互換に対応しているので,ss から tt への置換は NN 回の互換で表せることになる。よって, NN の偶奇と「ss から tt への置換のパリティ」は等しい。

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

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

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

人気記事
  1. 高校数学の美しい物語
  2. 8パズル,15パズルの不可能な配置と判定法