ホーム > 家族のギャラリー > ペントミノを解く > 第6章 ヘキソミノあれこれ > 1. 解き方

1. 解き方

解き方の基本はペントミノと同様で、箱（ボード）の中に順番にピースをはめ込んでいき、行き詰まったら最後のピースを剥がして別のピースを試していくという探索方法です。

高速化のために、無駄な探索を行わない探索枝の枝刈りを行っています。この方法はペントミノの高速化あれこれで試したものを使いました。基本的な技術は以下の通りです。

• ボード上の各セル毎に配置可能なピースとその方向を事前に洗い出しておく
• 上記を行う際に、６の倍数ではない閉じた空間ができないことを考慮する
• 上記を行う際に、ピース内の各セルの絶対座標を計算しておく
• 次のピースを置く空きセルが孤立スペースになっていないかチェックする
• ピースはボードの短辺に沿って配置したほうが高速なので、ボードが埋まってきたらピースの配置方向を切り替える

ボード全体を裏返すことを考えると２倍の解が求まってしまいますが、現時点ではそこまで考慮していません。