FLYING

〈全日本・紀文豆乳飲料シリーズ「麦芽コーヒー」の500ミリリットルパックを扱う小売店が少ないことに遺憾の意を表明する会〉活動記録

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

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

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

アルゴリズムの概要

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

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

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

2. 再帰を使って総当り

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

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

というのをC言語で書くと

構造体を値渡ししまくってたのをポインタ渡しにしたらかなり速くなった。関数呼び出しのオーバーヘッドって馬鹿にならないのなー。ただ、構造体のポインタを多用したせいでかなり読みにくいプログラムになってしまった。ソースコードは200行オーバーだし、いちから読む気は全く起こらんね。