先日から取り組んでいた以下の書籍を読みおわった。
- 作者: 坪崎誠司
- 出版社/メーカー: 株式会社プレスティージ
- 発売日: 2010/07/06
- メディア: 単行本（ソフトカバー）
- この商品を含むブログを見る
Chapter9まであって、1は順列の基礎、2～5までは順列の応用問題、6、7、9がバックトラック法による手順問題、8だけ異色の問題だった。
本を買った目的はアルゴリズムを学ぶことであって、全問解くことではなかったので、Chapter 1、2、6、8以外はパラパラと読んでおしまいにした。
今回苦労したのはChapter 8のリングを描こうというもの。
以下のように等間隔にならんだ9つの点のうち、4つの点を通る正円がいくつ描けるかという問題だ。
14個の円が描けるので、パズルを楽しみたい方は紙と鉛筆で考えてみると良い。
VBAでパズルの解く方法
書籍の解答では、座標を細かく切り分けて走査しするというもの。
1ピクセル進むごとに9つのそれぞれの点との距離を測り、見つかった数が4つなら、そこを中心に円を描く。
書籍のサポートサイトから解答プログラムをダウンロードして実行してみたが、実行にかかった時間は34.75秒。
ちょっと時間がかかりすぎだ。
今回のように点が等間隔の場合は、全ピクセルを走査する必要はなく、以下の赤点の場所だけチェックすればよい。
X軸、Y軸ともに120ピクセル分の走査なので、ループのステップを30に設定したところ、13.77秒で終了した。
ただ、点が等間隔でないときには応用が利かないので、書籍のやりかたのほうが汎用性があるといえる。
よりよい方法を求めて試行錯誤。しかし…
すべての座標から9つの点にアプローチするというのは、あまりエレガントな解決方法ではないように思える。
なぜなら、今回はたまたま120*120のループで済んでいるが、サイズが変わればループ回数も増大してしまう。
そこで、この問題を組み合わせ問題として解けないものか考えてみた。
つまり、9個の点のうち4つをとる組み合わせを列挙し、それぞれに対して円が描けるか描けないかを判定させるという方法だ。
しかし、結論から言ってこの試みは失敗した。
まず4点からの中心地を求める方法がわからない。
4点が正方形か長方形なら対角線の交わる位置で良い。
しかし、以下のようなケースでは、台形になってしまい、対角線ではダメだ。
そこで、次に円にぴったり収まる形に着目した。
- 正方形、長方形は円にぴったり収まる。
- 左右対称の台形も収まる。
- どのような左右非対称の台形も収まらない。
- どのような平行四辺形はも収まらない。
- どのようなひし形も収まらない。
しかしここで、上記のどれにも当てはまらない四角形では収まるケースと収まらないケースの違いが明確にできず、挫折した。
幾何学の知識があれば、もう少し頑張ったと思う。
