市原の新しい学習スタイル!
体験随時受付中! 10:00~17:00
Tel.0436-26-5267
お問い合わせメール   アクセス

マナビオからのお知らせ


公開日:2012-11-06

アルゴクラブの教材:I-Cubeの全体解は何通りあるのか?

先に公開した「アルゴクラブの教材:I-Cubeの4隅空けに解は何通りあるのか?」http://www.manabio.jp/kokuchi.php?id=40では、特定の空き配置のみを取り扱って、解が何通りあるのか示しました。

 今回は、もう一歩進めて、I-Cubeの完全解を求めてみたいと思います。アルゴクラブで使用するI-Cubeはパズルの世界では、「ペントミノ」と呼ばれる有名なパズルです。(ピースが立方体5つ(ペンタ)で構成されるのでこのような名称になっています。)ところが、インターネット上を探してみても、先に4つの空き位置を指定してから、解を算出方法はあるのですが、全体解について書かれたものは、全く見当たりませんでした。

「それでは、やってみよう。」
と思い、またもや、コンピュータを使ってやってみました。

 まず、4つの空きに着目して、I-Cubeの盤面8マス×8マスの中に4つの空きの置く最終状態が、何通りあるのか調べてみました。単純な話では、64個のマスから4個を抽出するので64!/60!=15,249,024通りが答えになります。但し、この答えの中には、回転したり、反転させたりすると同じ配置となる類似解が存在しています。では、この類似解を除いた解は、何通りなのでしょうか。

 参考例がなかったので、正直、随分遠回りをしました。多分2か月ぐらい思考錯誤をしていたと思います。難しかったのは、「パソコンで計算できる現実的なオーダーで解を得る方法」を探すことでした。

 始めは、重複を許したまま、4つの空きが作る4角形や3角形の周長を求めて、同じ周長同士をファイルに分類して、その中で重複を排除するような方法を模索していました。周長は4509通りあり、その内、一番多い周長には135,912パターンもありました。処理時間短縮の都合、重複判定だけは、パソコン本体のメモリ上で処理させたいと思ったのですが、考えつく限りの効率的な処理を考えましたが、抽出したパターンを記憶する処理の途中でどうしてもメモリオーバーとなり、重複判定ができませんでした。

 最終的に、後から重複を排除する方法をあきらめ、4つの空きを都度、既出かどうか判定しながら解をカウントする方法にしました。それまで1500万通りの空き状態を作る方法は、以下のようになっていました。
1.0から63の数字を並べて、スタート時点で0,1,2,3を選択します。
2.一番後ろの「3」を63まで1つずつコマを選択します。
3.後ろから2番目の「2」を「3」へ進め、一番後ろのコマを「4」から「63」まで1つずつコマを選択します。
4.後ろから2番目の「3」を「4」へ進め、一番後ろのコマを「5」から「63」まで1つずつコマを選択します。
5.この操作を繰り返し60,61,62,63までコマを選択します。このように、論理上、隙間なく最終状態を選択していきます。0から63は、8マス×8マスの盤面の左上を0にして下に向かって振られ、右下が63になる番号と考えます。ある時の4つの選択された数字を先頭からi,j,k,l(i<j<k<l)とします。この選択状態を8マス×8マスの盤面上で回転させ、改めて盤面番号を振って小さい数字順に並べてたものをi’,j’,k’,l’(i’<j’<k’<l’)とします。この時、i’j’k’l’がi,j,k,l、よりも小さければ、既に調べた選択と判定できます。この方法であれば、既出解をストックしなくても、回転させながら数字の大小を比較するだけで、既出解のある/なしを判定できるので、メモリーが足りなくなる心配はありません。

 効果は劇的でした!こうして抽出された「重複のない4つの空き」状態を解法プログラム(こちらもちょっと高速化しました)に渡して解をカウントしていきます。マナビオにある6台のパソコンにGoogleChromeというインターネット閲覧ソフトをインストールし、日中だけの作業で、わずか2日で完了することができました。1つのGoogleChromeで3,000から5,000パターン、1台のPCで3つのGoogleChromeを同時起動して算出させています。

 結論として、8マス×8マスの盤面に4つの空きを置く方法は、79,920パターンあり、この内、解が無い(=解数0)置き方を除くと、I-Cubeの最終状態は78,694パターンありました。解が無い置き方には、4つの空きで別の隙間を取り囲むような物理的に配置不可能なものが大半(1,223パターン)ですが、中には4つがバラバラにもかかわらず、解が無いパターンが3つだけありました。また、前回、調べた最小値、
「21通りより少ないパターンがあるのか?」
も気になっていました。確認したところ、解が21通り未満の配置パターンは、20通り×1パターン、19通り×2パターン、18通り×2パターンがあり、最小値は12通り×1パターンりでした。解の少なさで言えば、12通りが最難問ということになります。

 いつかこのHP上で成果を活用できるようにしたいと思っています。簡単なペーパーにも結果をまとめておきます。マナビオの会員の方で興味のある方は、お声かけ下さい。

 保護者の皆様もお子様と一緒にマナビオで探求してみませんか?

↑ トップページへ

← 戻る