Hatena::ブログ(Diary)

小人さんの妄想 このページをアンテナに追加 RSSフィード Twitter

2011-12-27

Scramble Squaresパズルを解く

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

f:id:rikunora:20111226124832j:image

f:id:rikunora:20111225113943j:image

虫の頭とお尻が描かれたプラスチックの板を、3x3の盤上に、ぴったりつながるように配置するというパズル。

盤面の縁には「3D SQUARES」と書かれています。

これ、一見簡単そうに見えるのですが、やってみると意外に難しい。

入手してからここ数年というもの、まだ1度も完成したことがありません。

そこで、パソコンの力を使って解いてみることにしました。


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

まずは、こんな方法を試してみました。

(1) 乱数でピース(プラスチックの板)を、いくつか適当に並べてみる。

(2) その中から、偶然つながっている箇所が多い結果を、いくつかピックアップする。

(3) ピックアップしたものを適当に変形、ピースを入れ替えてみる。

(4) 以下、(2)のピックアップと、(3)の変形を、延々解けるまで繰り返す。

要は、人間が試行錯誤で並べてみるのと同じことを、パソコンにやらせようというもくろみです。

遺伝的アルゴリズム」という方法に似ています。

(ただし、今回は交叉〜2つの結果を取り混ぜて1つの結果を作り出す、

という考え方が入っていないので「遺伝的アルゴリズムっぽい方法」です。)

上のようなプログラムを作って試したところ・・・なかなか答にたどりつきません。

このパズルには12カ所、虫がつながる箇所があります。

50万回繰り返してみたところ、12カ所のうち11カ所までつながる答は見つかったのですが、

本当の正解にはたどりつきませんでした。

これで、でたらめに試行錯誤を繰り返しても、簡単には解けないことがわかりました。。。


そもそも、このパズルには全部で何通りの並べ方があるのでしょうか?

まず、ピースは全部で9枚あるので、9枚の並べ方(順列)は 9! = 362880通り。

1枚のピースの向きは上下左右の4通りで、それが9枚あるので、4^9 = 262144通り。

ただし、盤面全体を上下左右にひっくり返すことができるので、各並べ方には4通りずつの重複があります。

かくして、全部の並べ方は、362880 x 262144 / 4 = 23781703680通り。

何と、約237億通りもの並べ方があるのです!

これでは50万回くらい試しても解けないわけだ。


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

(1) まず左上隅に1ピース置く。(置き方には4つの向きがある)

(2) その隣に、2枚目のピースを置く。(置き方には4つの向きがある)

(3) もし1枚目とうまくつながれば、その隣に3枚目のピースを置く。

  つながらなかったら、(1)に戻って次の向きを試す。

(4) もし3枚目がうまくつながれば、その隣に4枚目のピースを置く。

  つながらなかったら、(2)に戻って次の向きを試す。

     ・・・

(*) これを繰り返して、9枚目までうまくいったら、おしまい。

果たして、こんな「しらみつぶし」の方法で答が出るのか。。。

プログラムを作って、試してみたところ、何とほぼ一瞬で答が出ました!

f:id:rikunora:20111225113742j:image

プログラムC# で作りました >> ソースコード(Program.cs)

Visual Studio2010 Express で作ってありますが、短いプログラムなので、他言語にも簡単に移植できるでしょう。

プログラムが途中を検索する過程のログファイルは、こちら >> ログファイル(Result.txt)

この記録によると、たった 3603回で、全てのパターンを検索し終えています。

答は記録の中に"COMPLETE!"と書かれている箇所、上下左右の4箇所が出ていました。

つまり、答は1パターンしか無いということです。


さて、パズルを解いた後にウェブを検索してみると、、、

すでに同じようなプログラムを使って、このパズルを解いている人を見つけました。

Kevin R. Burgerという人、アリゾナ州立大でコンピュータを教えているらしい >> http://kevin.floorsoup.com/

解き方は、以下のPDFにありました。

* USING BACKTRACKING TO SOLVE THE SCRAMBLE SQUARES PUZZLE

>> http://kevin.floorsoup.com/scholarship/scramble/paper.pdf

解き方自体は私のプログラムと同じでしたが、こちらの方法では最初のピースを中央に配置しています。

中央にピースを配置してスタートすると、最初の1ピースは回転しなくても済む、ということ。

あと、中央にピースを配置した方が途中の制限がきつくなるので、探索回数はより少なくなっています。

やるなあ、ケビン。

ネットは世界につながっているのだと実感できた。


とねとね 2011/12/28 22:12 可愛いパズルですね。こんど誰かの誕生日プレゼントにしたいと思いました。そのうえ解法プログラムの公開ありがとうございます!

並べ方が何通りあるか数えているところは「場合の数」の問題として来月のセンター試験で出題されるかもしれないですね。最後に4で割るところを思いつくかどうかで正否が分かれそうです。

rikunorarikunora 2011/12/31 15:28 このパズル、模様を工夫して手作りでも作れるので、プレゼントには良いかと思います。
WEBで検索したのですが、これと同じものは見つかりませんでした。
もう売っていないのかもしれません。

センター試験(当時は共通一次)とは、もう我々には昔話かもしれませんが、
今になって見直すと、また別の視点で読めるかもしれませんね。
新・物理入門(増補改訂版):山本義隆
>> http://blog.goo.ne.jp/ktonegaw/e/8ea0ef12c20ef703b81afe2752b4c3a2

それでは、よいお年を!

アトムアトム 2012/01/10 23:47 デザインを変更したんですね。背景が白だと読みやすいですね。

rikunorarikunora 2012/01/12 09:27 新年に心機一転しました。
さっそくのコメントありがとうございます、やはり普通に白い背景が読みやすいですね。

ee 2017/04/02 14:11 そういやワンのタイルなんてものがありましたね

rikunorarikunora 2017/04/03 09:26 「ワンのタイル」検索してみたら、なるほどこれはおもしろい。
とりあえずこの解法プログラムに当てはめられそうです。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/rikunora/20111227/p1