# Magic Square by brute force

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.