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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: