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

マナビオからのお知らせ


公開日:2012-10-01

アルゴクラブの教材:I-Cubeの4隅空けに解は何通りあるのか?

先日、アルゴクラブ本部のHPに他校の生徒さんが考えた、I-Cube(アイキューブ)の4隅空けの解が60通り紹介されていました。(2012.9.22現在、ページは参照できないようです。)

I-Cubeは、8×8マスの中に5マス分のピース12個を敷き詰めていくパズルです。都合、64マス-12個×5マス=4マスは、必ず空いています。この4つの「空き」のとり方で難易度が変わります。4隅空けは、やや難しい(といっても経験則です。)部類に入ると思います。

その解として、60通りも提示されたので、
「スゴイなァ...」
と感心していました。そして、
「いったい、4隅空けには何通りあるのだろう?」
とネットを検索してみましたが、4隅空けの解の総数を見つけることはできませんでした。

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

 アルゴクラブのI-Cubeは、パズル界では「ペントミノ」と呼ばれる有名なものです。8×8マスの真ん中に4つ空きをつくる方法は、デイナ・スコットという数学者が1958年に65通りと証明しています。

 プログラムの処理は、12種類のピースをそれぞれ回転・反転(裏も使う為)した形状も含めて定義して、8マス×8マスの盤面上に指定した空きを避けて配置可能な位置にピースを置いて総当たりに試し、隙間のない配置から、既出の答えに類似がなことを確認しながら結果を表示するようになっています。敷き詰め型パズル問題のプログラムは処理自体は簡単なのですが、普通に処理すると、総当たりに解を探索する為に膨大な時間がかかってしまいます。そこで、早い段階で解にならない配置を排除(=最後まで処理せず途中でギブアップ)することが、処理上の「キー」となります。また、解が増えるにしたがって、類似解の探索にも時間がかかるようになる傾向があります。インターネットを検索すると、大学の理系学科の情報処理の課題などにもペントミノの問題は使われているようです。

 この真ん中空け65通りの解でプログラムの妥当性をチェックしている中で、面白い発見がいくつかありました。例えば、教室用教具の木製I-Cubeのピース名が書いてある面を表(自宅練習用ウレタン製のI-Cubeとは表が異なります。)とし、表のみで敷き詰めた場合、真ん中空けの65通りの中には、解はありませんでした。必ず、表裏が混在します。これは、意図されたものか分かりません。アルゴクラブの教室で木製I-Cubeの蓋を空けた時、4つの空きが外側に1マスだけずれているのは、こうした理由だと思います。また、自宅練習用ウレタン製I-Cubeの表のみを使用した場合、なんと、答えは1通りでした!

 さて、試行錯誤の末、マナビオで作ったプログラムでも8マス×8マスの盤の真ん中に2マス×2マスの空き条件だと、確かに65通りの解を出すようになりました。対称な空き指定でも同数解を算出し、ネット上に公開されている解とも一致したので、プログラムの結果を妥当と判断しました。そこで、4隅空けの条件を入れて、算出させました。

ピースの表裏混在の場合、4隅空けの答えは「2,170通り」でした!

でも、2,170通りって書かれても、多いのか少ないのか、良く分からないですね。そこで、空き位置を20パターン想定して、解の総数を算出してマナビオ独自に難易度を分けてみました。結果は、A3版1枚のペーパーにまとめてみました。保護者の方もマナビオで一緒に探究しませんか?興味のある方は、マナビオのアルゴクラブまで!

写真に解らしきものが一部映っていますが、これは、妥当性チェックの際の■途中■段階での解です。

↑ トップページへ

← 戻る