＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃ ペントミノの解を求めるプログラム May,1991. K.Mori ＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃ □概要□ 　″ペントミノ″というパズルを御存じですか？ 正方形を５つ繋ぎ合わせてできる図形 □□□□ □□□ □ □□ ↑こんなの や ↑こんなの これらは，全部で１２種類あります．それらの図形を１種類ずつ使って，６×１０の マス目を隙間なく埋めようというパズルです．ひまつぶしにはもってこいなのですが， 人間がやっていたのでは，すべての組み合わせを見つけ出すことはできません． 　そういうのは，パソコンにやらせようとなるわけです． □作成の動機□ 　最初は，リカーシブ（再帰）の例題にするため，Ｃ言語で記述しました．ＭＳ−Ｃ でコンパイルしたところ，かなりの処理速度を得ました．ところがＸＣでは，期待し たスピードは得られませんでした（ＭＳＣ＋２８６／１０ＭＨｚの４倍以上かかる）． そこで，「アセンブラで書いたら，Ｚ８０でもＸＣより速くなるのではないか」と思 い，作成してみました． □アルゴリズム□ （０） 　先に，ペントミノのブロックは，全部で１２種類あると述べましたが，これらのブ ロックに＄１〜＄Ｃの番号をつけます．さらに９０゜回転させたもの，対称形などを 組み合わせると，そのバリエーションは６３種類になります．これらの図形データを， 左上の正方形を基準（０，０）とし，４組の整数値で表わし，テーブルとして用意し ておきます． 例） ■□ 黒い正方形は，白い正方形から見て □ 左へ１つ，下へ０ □□ 左へ１つ，下へ１つ 左へ１つ，下へ２つ 左へ２つ，下へ２つの位置にある． → DEFB 1,0, 1,1, 1,2, 2,2 （１） この図形テーブルからデータを１つ取り出して，６×１０のマス目に置けるかどう かチェックしてゆきます．図形データは重複して使わないよう，既に使用済みのブロ ックは除かれます．また，マス目は，上から下，左から右に向かって埋めてゆくよう にします． （２） 取り出した図形が，指定の場所に置くことができれば，その場所にブロックの番号 を書き込んで，使用済みのフラグを立てて，（１）をコールします．そのブロックが ~~~~~~ 置けなければ，次のブロックのチェックとなります． （３） 　もし，指定の場所にどのブロックも置くことができなかったとすると，１つ前に置 いたブロックが間違いだったことになります．そこで，そのブロックをマス目から取 り除いて，（もちろん使用済みのフラグからも削除して）リターンします． ~~~~~~~~ （４） 　この手順で，すべての使用済みフラグが立てば（あるいは，サブルーチン・コール のネスティングが１２レベルに達した時），めでたく完成となります．完成図を画面 に出して，つぎの解を求めるためリターンします． ~~~~~~~~ 　完成図の表示は、都合上１〜Ｃの記号で行なわれます。例えば □ Ｃ □□□　ならば、　ＣＣＣ □ Ｃ といった具合です。 （５） 　（１）をコールするときに，現在チェックしているブロックの番号をスタックに積 んでおくので，リターンしてきたときは，続きのブロックからのチェックになります． これで，プログラム終了までにすべての解を求めることができます． このアルゴリズムの具体的な内容は，ソースリストを参照してください． □起動方法□ 　″ＳＷＯＲＤ″のコマンド・ラインから ＃　ＰＥＮＴＯＭＩＮＯ とキーインしてください．１つ目の解が出力されるのに１分程かかります． プリンタ出力される場合は， ＃　ＰＥＮＴＯＭＩＮＯ：／Ｐ としてください．画面表示と平行して，プリントアウトが行なわれます． □後味など□ 　時間がなかったので，最適化のようなものはやってません．すべての解（対称形な ど，重複するものを含んでいます）を表示するのに，４ＭＨｚで２日かかりませんで した．これでも充分ＸＣより速いですが，手を加えれば，さらに速くなるでしょう． 　時間があれば，正方形を立方体にして，３×４×５のかたまりをつくるパズル（３ Ｄペントミノとでも言おうか）に挑戦したいと思います． （ＥＯＦ）