Scramble Squaresパズルを解く - 小人さんの妄想

今回はサンタさんにもらった(?!)、こんな↓パズルを解いてみました。

虫の頭とお尻が描かれたプラスチックの板を、３ｘ３の盤上に、ぴったりつながるように配置するというパズル。
盤面の縁には「3D SQUARES」と書かれています。
これ、一見簡単そうに見えるのですが、やってみると意外に難しい。
入手してからここ数年というもの、まだ１度も完成したことがありません。
そこで、パソコンの力を使って解いてみることにしました。

解き方としてまっさきに思い付くのは「うまくつながるまで適当に並べてみる」という方法です。
まずは、こんな方法を試してみました。

(1) 乱数でピース（プラスチックの板）を、いくつか適当に並べてみる。
(2) その中から、偶然つながっている箇所が多い結果を、いくつかピックアップする。
(3) ピックアップしたものを適当に変形、ピースを入れ替えてみる。
(4) 以下、(2)のピックアップと、(3)の変形を、延々解けるまで繰り返す。

要は、人間が試行錯誤で並べてみるのと同じことを、パソコンにやらせようというもくろみです。
「遺伝的アルゴリズム」という方法に似ています。
（ただし、今回は交叉〜２つの結果を取り混ぜて１つの結果を作り出す、
という考え方が入っていないので「遺伝的アルゴリズムっぽい方法」です。）
上のようなプログラムを作って試したところ・・・なかなか答にたどりつきません。
このパズルには１２カ所、虫がつながる箇所があります。
５０万回繰り返してみたところ、１２カ所のうち１１カ所までつながる答は見つかったのですが、
本当の正解にはたどりつきませんでした。
これで、でたらめに試行錯誤を繰り返しても、簡単には解けないことがわかりました。。。

そもそも、このパズルには全部で何通りの並べ方があるのでしょうか？
まず、ピースは全部で９枚あるので、９枚の並べ方（順列）は 9! = 362880通り。
１枚のピースの向きは上下左右の４通りで、それが９枚あるので、4^9 = 262144通り。
ただし、盤面全体を上下左右にひっくり返すことができるので、各並べ方には４通りずつの重複があります。
かくして、全部の並べ方は、362880 x 262144 / 4 = 23781703680通り。
何と、約２３７億通りもの並べ方があるのです！
これでは５０万回くらい試しても解けないわけだ。

そこで、方針を改めて全部のパターンを順番に試してみることにしました。

(1) まず左上隅に１ピース置く。（置き方には４つの向きがある）
(2) その隣に、２枚目のピースを置く。（置き方には４つの向きがある）
(3) もし１枚目とうまくつながれば、その隣に３枚目のピースを置く。
　　つながらなかったら、(1)に戻って次の向きを試す。
(4) もし３枚目がうまくつながれば、その隣に４枚目のピースを置く。
　　つながらなかったら、(2)に戻って次の向きを試す。
　　　　　・・・
(*) これを繰り返して、９枚目までうまくいったら、おしまい。

果たして、こんな「しらみつぶし」の方法で答が出るのか。。。
プログラムを作って、試してみたところ、何とほぼ一瞬で答が出ました！

プログラムは C# で作りました >> ソースコード(Program.cs)
Visual Studio2010 Express で作ってありますが、短いプログラムなので、他言語にも簡単に移植できるでしょう。
プログラムが途中を検索する過程のログファイルは、こちら >> ログファイル(Result.txt)
この記録によると、たった 3603回で、全てのパターンを検索し終えています。
答は記録の中に"COMPLETE!"と書かれている箇所、上下左右の４箇所が出ていました。
つまり、答は１パターンしか無いということです。

さて、パズルを解いた後にウェブを検索してみると、、、
すでに同じようなプログラムを使って、このパズルを解いている人を見つけました。
Kevin R. Burgerという人、アリゾナ州立大でコンピュータを教えているらしい >> http://kevin.floorsoup.com/
解き方は、以下のPDFにありました。
* USING BACKTRACKING TO SOLVE THE SCRAMBLE SQUARES PUZZLE
>> http://kevin.floorsoup.com/scholarship/scramble/paper.pdf

解き方自体は私のプログラムと同じでしたが、こちらの方法では最初のピースを中央に配置しています。
中央にピースを配置してスタートすると、最初の１ピースは回転しなくても済む、ということ。
あと、中央にピースを配置した方が途中の制限がきつくなるので、探索回数はより少なくなっています。
やるなあ、ケビン。
ネットは世界につながっているのだと実感できた。