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 = 
| otherwise = u-l+1
where l = -minimum (:xs)
u = 9-maximum (:xs)
genGrid = do a <- [-9..9]
b <- [-9..9]
c <- [-9+max  (-a-b)..9+min  (-a-b)]
let diff = [,-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],
,
[d,b+d,-a-b-c]]

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

More Reading
Older// つの