「１５パズル」の攻略法～８パズル、３パズルへの還元

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

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

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

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

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

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

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

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

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

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

今日これから扱うのは、数独でも地雷でもなく、１５パズル（fifteen puzzle）

と呼ばれるものと、その仲間の８パズルだ。１年ちょっと前にＰＣが故障し

て、Ｖｉｓｔａマシンを購入すると、ガジェット（おまけソフト）として「ピクチャパ

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

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

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

４×４＝１６のマス目のうち、一つだけ空白で、そこを利用して１～１５の数

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

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

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

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

の話になるのは分かる。３×３＝９のマス目で、１～８の数字をスライドさ

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

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

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

ば理数系の私としては当然、「３パズル」まで考慮する。２×２＝４のマス

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

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

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

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

無難なサイトでは、神奈川県酒匂小学校のＨＰに、８パズルも１５パズルも

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

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

「解けない問題」が多数あるのでご注意あれ（下で例示）。Ｖｉｓｔａの方は、

Ｗｉｎｄｏｗｓサイドバーを表示してガジェットで遊ぶのが便利で楽しいと思う。

　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

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

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

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

　左図が、２×２＝４のマス

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

　流石に出来ない人はいな

　いだろうが、この記事に

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

　赤い矢印に沿って

　数字をスライドし、

　①から⑥の順に進

　めて行けば、簡単

　に完成する。結局、

　３つの数字を右に

　回転させた形になっ

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

の記事と同様だ。

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

　左のように、完成形の１と２を入れ替え

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

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

　似た話は８パズルや１５パズルにもあっ

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

問題は解けないのだ（不可能な配置）。

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

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

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

Ｐ．Ｓ．　３年半後、証明記事をアップした。

　　　置換・互換と１４－１５パスルの不可能性～３パズル、８パズルからの証明

　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

続いて、８パズルについて。これは、上側と左側の列（合わせて５マス）を先

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

　完成形では、上側に

　１，２，３、左側に

　１，４，７と並んでる

　から、先にこれら５

　つ（１は重複）を定

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

の都度、動かしたい数字を含む適当な長方形（ｏｒ正方形）のグループに

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

上側に１，２，３と並んだ状態を目指すと、たまたま左側も１，４，７と並ん

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

右下の３パズル（２×２＝４マス、数字は５，６，８）を揃えて、完成となる。

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

　線部分の入れ替え（互換）はど

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

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

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

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

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

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

　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

いよいよ最後は、一番標準的な１５パズル（４×４＝１６マス）について。

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

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

見てみよう。

この問題は、実際にＶｉｓｔａのガジェットで最初に出たもので、都合のいい

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

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

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

　ちなみに、この１５パズルでも、次

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

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

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

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

　（☆追記：　上述の通り、既に証明。）

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

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

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

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

明してみたい。

以上、１５パズルを８パズルへ、さらに３パズルへと還元して解く方法につ

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

記事のポイントだ。

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

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

Ｐ．Ｓ．１５パズルの解けない問題で、１１と１２の代わりに、１４と１５を

　　　　入れ替えたものは、「１４－１５パズル」と呼ばれて、１００年ほど

　　　　前にサム・ロイド（Sam Loyd）が１０００ドルの賞金をかけたらし

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

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

ｃｆ．Ｖｉｓｔａのお遊びソフト、「１５パズル」を攻略

　　Ｗｉｎｄｏｗｓの地雷ゲーム、「マインスイーパ」の簡単な攻略法

　　ニコリの数字パズル､「数独」に初挑戦（難易度４、朝日新聞）

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

　　スイス職人の遊び心～オイラー生誕３００年腕時計の｢数独」文字盤

　　最高難易度５もクリア☆人気パズル「数独」早くも卒業（朝日新聞・ｂｅ）

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