ホーム > 家族のギャラリー > ペントミノを解く > 第5章 C言語版の高速化あれこれ > 4. Xピースによる解の重複排除<

4. Xピースによる解の重複排除

6×10のボードにはめ込むペントミノでは単純に計算すると、一つの解を180度回転させたケースと、裏返したケースで、実際の解の数の4倍の答えが見つかってしまう。これを避けるためには、全ての解を求めてから重複を排除してもよいが、まず4倍の解を求めるために時間がかかってしまう。

そこで180度回転させても、裏返しても一通りのパターンしか持たないXピースに着目して、このXピースを置く場所をボードの左上1/4のエリア(7ヶ所)に限定させて、ボードの回転や反転の重複を避けます。このアイデアは昔、Webで見つけたものです。

プログラムを単純化するために、一つ目にXピースを配置してから、残り11種類のピースのはめ込み探索を行うようにしています。7箇所全てで探索が終われば、全ての解が求まったことになります。

図4-1 Xピースによる反転、回転解の排除

【↑高速化インデックスへ】