15パズルの線形代数

MacOSXのDashboardにタイルゲームなるものがある.

これはWindowsVista以降に搭載されている(Macユーザーなので真偽は知らない)15パズルと同じものだ.

ピクチャーパズルとも言う.

僕は昔からこれが苦手で,本当に嫌いだった.

久々にこのゲームをやってみたらやはり諦めてしまった.

でも今は多彩(?)な数学を用いてこれを解析してやろうと燃えていた.

とりあえずの目標はこれ.

photojigsaw

調べてみたら,Mathematicaで実装されているnb(notebook)を見つけた.

Picture Puzzle from the Wolfram Demonstrations Project by Yu-Sung Chang

さあ,研究しようと思って,遊んでいたら,早速解けない場面に遭遇.
ふざけんな死ね

考えてみる.今の盤面だと,あと(11,12)を交換すればクリアできる.

このゲームで許される操作は,白マスを16として,16を含んだ隣接互換のみ.(しかも境界条件つき)

ということは,古典的なswap操作,12を一瞬テンポラリーである16に格納して,11と16を交換し,最後に12を戻して来ればよい.

互換としては(12,16)(11,16)(12,16)をすればいいはずだが,

ぐぬぬ...出来ないではないか.最後の(12,16)が出来ない.これは隣接互換条件からくる.

よくよく考えてみると,16(白マス)が元の場所に帰って来ないといけない,という条件を忘れていたことに気づく.

つまり,クリアのためには,「(12,16)(11,16)(12,16)の互換」かつ「16(白マス)が元の場所に帰ってくる」が必要.

16が元の場所に帰ってくるためには,偶数回の互換が必要だろう.偶置換.

でも,(12,16)(11,16)(12,16)の互換は見た通り,奇置換だ.

 

…はい,解けません!!

 

このnbの作者は,単純にシャッフルしてるだけですわ...萎えた.

で,ググってたら,出るわ出るわ,「15パズル 不可能な配置」「偶置換,奇置換」

 

でも,その中に興味深いエントリを発見.15パズルの必勝法,と題されている.これは凄い.

 

さらには,Wikipedia には

 

15パズルは任意の可能な配置へ80手以内で変形できる。80手が必要な配置は存在する。

n×nパズルにおいて、最短手数を求める問題はNP困難である。最短手数の定数倍の変形を求める多項式時間アルゴリズムが提案されている。

 

と記されていて,パズルとしても研究され尽くしていることが分かった.

 

今日から15パズルなんか怖くないぞ!!

 

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中