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パズルなんか怖くないぞ!!

 

広告

任意の凸四角形は長方形に出来る

元々この問題を考えたのは,

数学セミナー12月号(だったと思う)の「エレガントな解答を求む」のコーナーで

Dudeneyの三角形を知ったからだ.

Dudeneyの三角形とは,

正三角形を4つのピースに切り分け, 再配置して正方形を作れるか

という,英パズル作家のDudeneyのクイズ.

この作図は非常に難しいが,感動する.

そうして,色々調べていたら,

四角形を分割して正方形にする

というサイトに遭遇.これまた感動的な再配置を多数学ぶ.

特に,任意の四角形が長方形に出来る,ということを知った.

そして,どうせなら自分でflashを作ってみようと思った.作った.

http://schch.net/jimako/tetragon.swf

実装にあたり,Tween24というライブラリを使ってみた.これは回転と平行移動を同時に実現するトゥイーンをスクリプトで書くため.

基本的に使いやすかったのだけれども,やはり個人的には「デザイン屋のおもちゃ」という感じがした.

変形過程で,serialとしたのはparallelでうまくいかなかったから.

回転と同時に移動,みたいな難解なアクションは

(いくらTween24が素晴らしいライブラリでも)座標計算が難しい面倒なので

結局serialにして$$xyに頼りましたとさ.

ただ,完全に(回転&平行)移動終了後に頂点の座標を取得しようとすると,

回転前座標に平行移動座標を加えただけで,座標の回転操作がされていないみたいで,

これ以上機能盛り込むことが出来なかった.意味不明.

時間ができたら調べてみたいが,多分もうない.

ソースコードは続きにて.

“任意の凸四角形は長方形に出来る” の続きを読む

中学生でも分かるabc予想( ^ω^)

最近,abc予想が巷で噂になってるけど,

僕の中学生の教え子でも,関心を持つ子がいて,少し嬉しく思ったお( ^ω^)

でも,abc予想の「内容」まではメディアでは報道されなくて,

検索してもそこまで分かりやすい文章があるとは思えなかったので,

自分なりに簡単に説明してみたお( ^ω^)

“中学生でも分かるabc予想( ^ω^)” の続きを読む