ジグソーパズルくらいでパソコン使うなよ、夏

という訳で、パソコン甲子園 2006年度予選の例題10を解くプログラムが遂に完成しますた。ジグソーパズルの枠とピースの組み合わせが複数与えられ、それぞれのピースの組み合わせについて、パズルを完成させることができるかどうかを判定するというもの。

これで2006年度予選の問題は全て解いたことになるから、あとは2006年度の本選の方に挑戦するつもり。1つのプログラム書くのにかかる時間をもっと短縮しないと、本番では役に立たなそうだなあ。

アルゴリズムの概要

1. ピースを候補が少ない順にソート

まず、枠にピースを何もはめていない状態で、それぞれのピースを置くことが出来る場所の数 = 候補数を取得する。ただし、ピースを回転する場合は別の候補として処理する。その後、そのデータを元にして、ピースを候補数が少ない順にソートする。

例えば、候補が1つしかないピースがあるとすれば、この方法で真っ先に場所を確定することができ、その後に続くピースの候補数を減らすことができる。実際のジグソーパズルでも角などの候補が少ないピースからはめていくように、簡単そうなところから完成させていく方針を取った。

2. 再帰を使って総当り

再帰処理を使って総当りで候補をチェックする。ピースを置く場所の候補が複数あるときは、適当に置く場所を決定して次のピースが置けるかどうかチェックする。もし次のピースを置くことができなければ、いったん戻って、前のピースを置く場所を再検討し、他の候補を試してみる。こういうのをバックトラックというらしいがよく知らない。

試行錯誤しながら盤面を埋めていき、ピースを使い切って盤面を埋めることが出来れば、ピースの組み合わせが正しいと判定する。最後まで盤面が埋まらないときや、ピースが余ってしまう場合は組み合わせが間違っていると判定する。