This was inspired by Tsoder’s video https://www.youtube.com/watch?v=Qf4NyHiy0W8 where he generated all the 3×3 magic squares by brute force, generating all permutations of 1-9 and rejecting the ones which were not magic squares.
My first reaction was that that was not brute force; this was brute force:
squares = [[[a,b,c],[d,e,f],[g,h,i]] |
a <- [1..9],
b <- [1..(min 9 (14 - a))],
b /= a,
c <- [15 - a - b],
c <= 9,
not $ elem c [a,b],
d <- [1..(min 9 (14 - a))],
not $ elem d [a,b,c],
e <- [1..(14 - (maximum [a,b,d]))],
e <= 9,
not $ elem e [a,b,c,d],
f <- [15 - d - e],
f < 15 - c,
not $ elem f [a,b,c,d,e],
g <- [15 - a - d],
c + e + g == 15,
not $ elem g [a,b,c,d,e,f],
h <- [15 - b - e],
not $ elem h [a,b,c,d,e,f,g],
i <- [15 - c - f ],
g + h + i == 15,
a + e + i == 15,
not $ elem i [a,b,c,d,e,f,g,h]
This turned out to be faster than Tsoder’s method, because permutations are rejected as early as possible. After reorganising, it was even faster:
squares' = [[[a,b,c],[d,5,f],[g,h,i]] |
a <- evens,
b <- odds,
c <- [15 - a - b], -- row 1
(c /= a) && (c > 1) && (c < 9),
h <- [10 - b], -- col 2 -- h /= b because b /= 5
i <- [10 - a], -- diag 1
i /= c,
g <- [15 - h - i], -- row 3
not $ elem g [a,c,i],
g == 10 - c, -- diag 2
d <- [15 - a - g], -- col 1
elem d odds,
not $ elem d [b,h],
f <- [10 - d], -- row 2
f == 15 - c - i, -- col 3
not $ elem f [b,d,h]
]
where evens = [2,4,6,8]
odds = [1,3,7,9]
In next week’s exciting episode, I attempt to combine the two approaches.
Great Wall 