Problem 275

Problem 275 - Project Euler

問題の概要.
ある条件を満たす,polyominoを探す.
その条件の1つは,横方向にバランスがとれていること(重心のx座標が0).
詳細な条件は上のリンクで.
絵でみると分かりやすい.
下図はproject eulerからの引用.

求めるのはサイズ18.しかし,形が想像できないので,ナイーブな検証用のコードをC++で書いた.
実行したら,サイズ15で4 秒ぐらいだった.これなら,サイズ18でも大丈夫か,と思い,サイズ18で実行したら,
見事に1分以上かかった(3分ぐらい).

ナイーブな方法でもうまく,枝刈りをすれば,1分切れるかもしれないが,もっと賢い方法がありそう.

ひさびさに,難問か?

追記

どうにかして,Haskellで速いコードを書こうと思っていた.
しかし,こういうのはどうも,書きづらい.問題が難しいからでもある.
この手の問題は可変配列を使うのが単純で効率的だろう.しかし,STArray使うのは,なんというか負けな気がする
(STArray使うくらいなら,C++で書く).

どうにかして,純粋関数型言語的に書けないのかなー.