Problem 166

http://projecteuler.net/index.php?section=problems&id=166

魔方陣のような問題(同じ数字が何度出てもかまわない）
brute force でもできるが、それでは面白くない。
とりあえず、数字をmod 2 して考えると自明解のほかに

1 0 0 0 
0 0 1 0 
0 0 0 1 
0 1 0 0

が存在することが分かる。
上や、上の回転などしたものを解から引いても、まだ各和は等しい。

main = print.sum.map (product.map count) $ genGrid

count xs | u < l = 0
         | otherwise = u-l+1
    where l = -minimum (0:xs)
          u = 9-maximum (0:xs)

genGrid = do a <- [-9..9]
             b <- [-9..9]
             c <- [-9+max 0 (-a-b)..9+min 0 (-a-b)]
             let diff = [0,-b,-c,a+b,a-c,-b-c]
             d <- [-9+maximum diff..9+minimum diff]
             return [[a,-b-d,-b-c-d],
                     [b,-c-d,a+b-d],
                     [c,c+d,-a+c+d],
                     [d,b+d,-a-b-c]]

計算量は高々19^4≒10^5。まぁ、これなら大丈夫（実際はc,dの範囲は19よりも小さいし）。