« 10年8月の全走行距離&『ホタルノヒカリ2』第9話 | トップページ | 多剤耐性細菌は怖い・・秋バテの身体は重い・・ »

「15パズル」の攻略法~8パズル、3パズルへの還元

ある程度の予想はついてたけど、どうも世の中にはパズル好きが大勢

らっしゃるようだ。理屈や脳トレの好きな人が、お遊び気分で楽しめるゲー

ってことで、私も好きな方だろう。ただ、ゲームをやり出すと、時間とエネ

ルギーを浪費する感じがあるから、大人になってからはなるべくやらないよ

うにしてた。どうせなら、もっと学問的に高度なことで遊ぶ方が、やりがいも

あるし頭も鍛えられる。自分にとっての世界も広がっていくわけだ。

     

とはいえ、毎日更新するブロガーとして考えると、気楽に書ける理屈系のネ

タとして、なかなか捨てがたい魅力があるのは確か♪ 実際、数独関連の

記事(計4本)へのアクセスはわりと多いし、地雷ゲーム・マインスイーパの

記事にも地味なアクセスが続いてる。

                   

今日これから扱うのは、数独でも地雷でもなく、15パズル(fifteen puzzle)

と呼ばれるものと、その仲間の8パズルだ。1年ちょっと前にPCが故障し

て、Vistaマシンを購入すると、ガジェット(おまけソフト)として「ピクチャパ

ズル」と呼ばれるものが入ってた。15枚の正方形に分割された絵を並べ

替えるのだから、1~15の数字を並べ変えるパズルと本質的に同じこと。

実際、ピクチャパズルの設定を変えると、外観が15パズルに変化する。

4×4=16のマス目のうち、一つだけ空白で、そこを利用して1~15の数

字をスライドさせていくものだ。やったことがある人が少なくないだろう。

          

で、そのピクチャパズルとか15パズルについて記事を書いた所、しばらく

前、「8パズル」への検索アクセスが時々入ってたのだ。最近は入ってない

けど、15パズルを理論的に考えると、かなりの部分、より簡単な8パズル

の話になるのは分かる。3×3=9のマス目で、1~8の数字をスライドさ

せる8パズルへと、15パズルを「還元」することがかなり可能なのだ。しか

も、単なる学問的研究ではなくて、15パズルの具体的解き方とも関係ある。

      

そこで今日は、15パズルと8パズルについて考えてみよう。もちろん、半

ば理数系の私としては当然、「3パズル」まで考慮する。2×2=4のマス

目で、1~3の数字をスライドするもので、英語版のウィキペディアでさえ

扱ってないし、検索してもハズレばかりだけど、一般的に考えればそこま

で行き着くのは当たり前だろう。同種のものの中で最小なんだから。。

       

なお、パズルは厚紙で作ってもいいし、ネットで検索してもすぐ出て来る。

無難なサイトでは、神奈川県酒匂小学校のHPに、8パズル15パズル

あるし、マンガの絵を使った15パズルもすぐヒットする(完成図の予想に

やや苦労)。手書きで問題を「解く」のはいいけど、問題を「作る」場合は、

「解けない問題」が多数あるのでご注意あれ(下で例示)。Vistaの方は、

Windowsサイドバーを表示してガジェットで遊ぶのが便利で楽しいと思う。

      

          

        ☆          ☆          ☆

では、まず最も簡単な「3パズル」からスタートしよう。簡単過ぎて、ネット

では相手にされてないようだけど、8パズルや15パズルを射程に入れて

考えるなら、十分意味はある。

     

100903a

 左図が、2×2=4のマス

 目を使った、3パズルだ。

 流石に出来ない人はいな

 いだろうが、この記事に

おける説明の書き方を示すためにも、一応解答を掲載しよう。

     

100903b

 赤い矢印に沿って

 数字をスライドし、

 ①から⑥の順に進

 めて行けば、簡単

 に完成する。結局、

 3つの数字を右に

 回転させた形になっ

てるので、後の議論でも「回転」という言葉を使う。以前のピクチャパズル

の記事と同様だ。

     

この3パズルの段階で、既に「解けない問題」が色々と存在する。例えば

100903c

 左のように、完成形の1と2を入れ替え

 た問題は解けないし、これを回転させ

 たりスライドさせた問題も当然解けない。

 似た話は8パズルや15パズルにもあっ

て、要するに、完成形で左右に隣り合った2つの数字を入れ替えただけの

問題は解けないのだ(不可能な配置)。

        

この入れ替えは、大学レベルの「線形代数」(行列に関わる理論)で「互換

と呼ばれてる。解けないことの数学的証明には、この線形代数の理解が必

で、今回はとりあえずパスしとこう。。

  

  

P.S. 3年半後、証明記事をアップした。

   置換・互換と14-15パスルの不可能性~3パズル、8パズルからの証明

      

             

         ☆          ☆          ☆

続いて、8パズルについて。これは、上側と左側の列(合わせて5マス)を先

に揃えてしまえば、残りは3パズルになる。具体例を見てみよう。

     

100903d

 完成形では、上側に

 1,2,3、左側に

 1,4,7と並んでる

 から、先にこれら5

 つ(1は重複)を定

位置に移動させればいい。解答例は次の通りだ(やり方は多数存在)。

の都度、動かしたい数字を含む適当な長方形(or正方形)のグループに

注目して、左右に回転させればいい。

      

100903e

    

上側に1,2,3と並んだ状態を目指すと、たまたま左側も1,4,7と並ん

でくれる。もちろん、こんなラッキーがなくても大丈夫だ。最後は、残った

右下の3パズル(2×2=4マス、数字は5,6,8)を揃えて、完成となる。

      

一方、3パズルの時と同様に、次のような8パズルは解けない問題だ。赤

100903f

 線部分の入れ替え(互換)はど

 うしようもない。私ももちろん、

 最初はそんな問題があること

 に気付かなかったから、電車

 内で適当にノートに問題を書い

  て、「解けない・・あとちょっとな

のに・・」とか考え込んだわけだ♪ ま、わりと早めに気付いたけど。。

       

             

         ☆          ☆          ☆

いよいよ最後は、一番標準的な15パズル(4×4=16マス)について。

これは、上側と左側の列(合わせて7マス)を先に揃えてしまえば、残りは

8パズルになる。そして更に、3パズルまで持って行けるのだ。具体例を

見てみよう。

         

100903g

    

この問題は、実際にVistaのガジェットで最初に出たもので、都合のいい

ものを選択した訳じゃない。ネットの問題も含めて、他に5問ほど実験。全

て簡単に成功している。より良い解法にこだわるのでなければ、「数独」と

違って、ほとんど悩むことのない機械的作業だ。

           

100903h_2

 ちなみに、この15パズルでも、

 のような問題は解けない(赤線部

 に注目)。これが解けないことの理

 由や証明については、いずれ後続

 記事で扱いたいと思ってる。

 (☆追記: 上述の通り、既に証明。)

          

一応、ウィキペディアの外部リンクで、数学的説明のページに飛べるように

なってるけど、かなり省略されたものだし、パズルと線形代数の両方をよく

理解してないと、何となく頷くだけに終わってしまうだろう。これは、学問の世

界(特に数学・論理学)では危険なことだ。ウチではもっと細かく具体的に説

明してみたい。

             

以上、15パズルを8パズルへ、さらに3パズルへと還元して解く方法につ

いて簡単に説明した。この3種を関連付けて、具体的に解いた点がこの

記事のポイントだ。

それでは、今日はこの辺で。。☆彡

  

      

      ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

P.S.15パズルの解けない問題で、11と12の代わりに、14と15を

    入れ替えたものは、「14-15パズル」と呼ばれて、100年ほど

    前にサム・ロイド(Sam Loyd)が1000ドルの賞金をかけたらし

    い。当時としてはかなり高額なんだろう。ま、絶対に解けないこと

    は既に分かってたらしいけど。。♪ (英語版ウィキを参照)

        

           

cf.Vistaのお遊びソフト、「15パズル」を攻略

  Windowsの地雷ゲーム、「マインスイーパ」の簡単な攻略法

  ニコリの数字パズル、「数独」に初挑戦(難易度4、朝日新聞)

  天才オイラーも苦戦したラテン方陣~ニコリ「数独」の源流

  スイス職人の遊び心~オイラー生誕300年腕時計の「数独」文字盤

  最高難易度5もクリア☆人気パズル「数独」早くも卒業(朝日新聞・be)

  算数まじりの四角いジグソーパズル、「スクエアカット」(朝日新聞・be)

|

« 10年8月の全走行距離&『ホタルノヒカリ2』第9話 | トップページ | 多剤耐性細菌は怖い・・秋バテの身体は重い・・ »

「ゲーム」カテゴリの記事

数学」カテゴリの記事

コメント

はじめまして、こんばんわ。
ガリレオで検索して以来お気に入りにしています。
15パズルにもルービックキューブみたいに
最短手数があるのでしょうね

投稿: けろよん | 2010年9月 5日 (日) 19時19分

> けろよん さん
    
はじめまして。コメントありがとうございます♪
『ガリレオ』以来のお気に入り登録、嬉しいです。
   
それにしても珍しいですね☆ この種の記事についた
短いコメントで、挨拶文と改行が入ってるのは。
キッチリした文章なのに、名前はけろよんさん(笑)
すごくイイと思います。
    
    
さて、「最短手数」。解ける問題には当然あるはずです。
個々の問題ではなく、一般的な最短手数、つまり、
すべての問題を解くための最短手数については、
ウィキペディアにこう書いてあります。
    
  「8パズルは任意の可能な配置へ31手以内で
   変形できる。31手が必要な配置は存在する。
   15パズルは任意の可能な配置へ80手以内で
   変形できる。80手が必要な配置は存在する」
   
ただ、証明は、個々の問題についてであっても、
コンピューターを使わないと困難でしょう。
ましてや、一般論だと、先日のルービック・キューブの
最短手数20手みたいに、コンピューターで
しらみつぶしにするしかないと思います。
   
ちなみにあのルービック・キューブの証明。
まだ検証されてないと思いますが、報道機関も含め、
みんな既に信じてるようですね。     
円周率5兆ケタの方は、まだ保留気味なのに♪
   
僕は、自分が納得するまでは、「参考」程度に
思ってます。少なくとも、自分にとっては。
その意味で、フェルマーの定理もポアンカレ予想も、
解決された「と言われてる」だけのこと。
本当に理解できてるのは専門家のごく一部だろうし。。
    
ただ、3パズルなら、自分で解いて確信してます。
最初の配置は24通り(4×3×2×1)で、
そのすべては6手以内で解ける。
6手かかるのはただ一つ。
左上0、右上3、左下2、右下1の場合です。
       
ま、8パズル以上は証明する気がしませんけどネ♪ shine

投稿: テンメイ | 2010年9月 5日 (日) 23時02分

はじめまして、名無しでスイマセン。

わたしは、任意問題の最短手数をPCに解かせ様と、
参考に成る資料が無いかと調べていて、最終的に
takakenさんの
「PDBを使った15パズル自動解答プログラム」
と、言う記事に辿りつたのですが、わたしには、
高度過ぎて、半部程しか内容を理解出来ず、
実装も大変そうだったので「最短手数」は、
あきらめて、簡易解法的な定番手法でどうにか
出来ないものかと、わしもほぼ同じアプローチで
15パズルの解法を考えていたのですが、
なんだか上手く方法論を築けず、再びネットに
頼って見た処、この記事にたどり着きました。
大変参考に成り分りやすかったです。
これで思う物が、作れそうです。
それで、本文にあった後続記事も読みたいと思い
検索してみたのですが、それらしい記事への
ヒットが無かったのですが、書かれていないのでしょうか?

投稿: | 2013年4月18日 (木) 23時17分

> 名無し さん
   
こんばんは。これまた珍しいコメントですね。
名無しなのに丁寧で、挨拶どころか
「スイマセン」とまで書いてらっしゃる。
そこまで行けば、あと一歩ですよ。
ハンドルネームを書くだけで、印象は全く違います。
   
で、この2年半前の記事がお役に立てたようで、
光栄です。自分で読んだのも2年半ぶりかも。  
   
後続記事が書けてないのは、色々理由がありますが、
一番問題なのは、線形代数のテキストや問題集が
どこかへ行ってしまったこと。
持ってるのは間違いないから、新たに買うのも
気が引けて、話が進まないわけです。
   
今現在はもう、ドラマ『ガリレオ』その他で
6月末まであおられるので、当分無理ですね。
3年後くらいなら、書いてるかも知れません。
  
ウチは総合サイトなもんで、悪しからずご了承を。。shine

投稿: テンメイ | 2013年4月20日 (土) 01時10分

コメントを書く



(ウェブ上には掲載しません)




« 10年8月の全走行距離&『ホタルノヒカリ2』第9話 | トップページ | 多剤耐性細菌は怖い・・秋バテの身体は重い・・ »