SQL Puzzles – Magic Squares

I love logic puzzles.  That’s not to say I’m good at them, but I enjoy problem solving enough that I went into IT as a career.

Matthew McGiffen started a series of puzzles for people wanting to improve their SQL skills over on his blog.  The first one is a magic puzzle.

magicsquare3

The basic goal is to take a 3×3 grid and put into it the numbers 1 to 9, where the columns, rows and diagonals all add up to the same result.

Have a look at Matthew’s post, and have a think of it for yourself and we’ll go over my solution 🙂

 

 

So, you’ll see in Matthew’s comments section that there are a few people who went with an iterative approach, which would be typical programming logic.  It also takes up to 10 minutes(!) to brute force all the results this way.

I have a solution in his comments, but I wanted to discuss why I came up with it.

So, I went with a Set-based approach.  SQL is great at performing on sets of data.  Tables, resultsets in a optimal matter.  I remember an Itzik Ben-Gan talk at SQL Code Camp Downunder Oz several years ago, where he went over the difference in performance between cursors and loop-based logic and set-based, and it’s stuck with me ever since.  So, the first thing I do is try to figure out a set-based approach.

Here is my initial solution, I posted on Matt’s blog.

DECLARE @nums TABLE (n TINYINT)

INSERT INTO @nums (n)
VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9)

SELECT n1.n n1, n2.n n2, n3.n n3,
       n4.n n4, n5.n n5, n6.n n6,
       n7.n n7, n8.n n8, n9.n n9
FROM @nums n1
    JOIN @nums n2 ON n2.n <> n1.n
    JOIN @nums n3 ON n3.n NOT IN (n1.n, n2.n)
    JOIN @nums n4 ON n4.n NOT IN (n1.n, n2.n, n3.n)
    JOIN @nums n5 ON n5.n NOT IN (n1.n, n2.n, n3.n, n4.n)
    JOIN @nums n6 ON n6.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n)
    JOIN @nums n7 ON n7.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n)
    JOIN @nums n8 ON n8.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n)
    JOIN @nums n9 ON n9.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n)
WHERE (n1.n + n2.n + n3.n) = (n4.n + n5.n + n6.n) 
    AND (n4.n + n5.n + n6.n) = (n7.n + n8.n + n9.n) 
    AND (n1.n + n2.n + n3.n) = (n1.n + n4.n + n7.n)
    AND (n1.n + n4.n + n7.n) = (n2.n + n5.n + n8.n) 
    AND (n2.n + n5.n + n8.n) = (n3.n + n6.n + n9.n)
    AND (n1.n + n2.n + n3.n) = (n1.n + n5.n + n9.n) 
    AND (n1.n + n5.n + n9.n) = (n3.n + n5.n + n7.n)

That solution runs in ~250ms.  A lot better than the 10 minutes that the loop-based method takes 🙂

Can we make it better?

I was thinking about this and I came up with a solution.  We’re still brute forcing all the combinations of the numbers in that

So, basically, you have the resulting correct dataset, and you have four rotations of the data.  The rotations are where the numbers rotate 90-degrees from rows to columns, then 180-degrees (so the top row becomes the bottom row) and then 270-degrees.

There is also reflections – the correct result is the same when you swap out column 1 and column 3, so the numbers read forwards and backwards, for all four rotations.

So, we know there are 8 solutions, and if you run that SQL, you will see them.

 

Basically, if we still assume we don’t know any of the correct sequence of numbers, we still have to brute force the first solution – the initial solution without rotations or reflections, and then we can perform the rotations and reflections.

In the initial solution, we’re finding all combinations of the numbers 1 – 9.  The resultset is 362,880 rows of data.

If we find the first result, it comes in at around the 21,814th row.

So, if we take that result at 21,814 and add the 8 rows we need to calculate, then we come in significantly fewer checks than brute forcing the whole result.

DECLARE @nums TABLE(n TINYINT)
DECLARE @n1 TINYINT, @n2 TINYINT, @n3 TINYINT, 
        @n4 TINYINT, @n5 TINYINT, @n6 TINYINT, 
        @n7 TINYINT, @n8 TINYINT, @n9 TINYINT

INSERT INTO @nums (n)
VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9)

SELECT TOP(1) @n1 = n1.n, @n2 = n2.n, @n3 = n3.n,
              @n4 = n4.n, @n5 = n5.n, @n6 = n6.n,
              @n7 = n7.n, @n8 = n8.n, @n9 = n9.n
FROM @nums n1
     JOIN @nums n2 ON n2.n <> n1.n
     JOIN @nums n3 ON n3.n NOT IN (n1.n, n2.n)
     JOIN @nums n4 ON n4.n NOT IN (n1.n, n2.n, n3.n)
     JOIN @nums n5 ON n5.n NOT IN (n1.n, n2.n, n3.n, n4.n)
     JOIN @nums n6 ON n6.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n)
     JOIN @nums n7 ON n7.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n)
     JOIN @nums n8 ON n8.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n)
     JOIN @nums n9 ON n9.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n)
WHERE (n1.n + n2.n + n3.n) = (n4.n + n5.n + n6.n) 
  AND (n4.n + n5.n + n6.n) = (n7.n + n8.n + n9.n) 
  AND (n1.n + n2.n + n3.n) = (n1.n + n4.n + n7.n)
  AND (n1.n + n4.n + n7.n) = (n2.n + n5.n + n8.n) 
  AND (n2.n + n5.n + n8.n) = (n3.n + n6.n + n9.n)
  AND (n1.n + n2.n + n3.n) = (n1.n + n5.n + n9.n) 
  AND (n1.n + n5.n + n9.n) = (n3.n + n5.n + n7.n);

SELECT @n1, @n2, @n3, @n4, @n5, @n6, @n7, @n8, @n9
UNION SELECT @n7, @n4, @n1, @n8, @n5, @n2, @n9, @n6, @n3
UNION SELECT @n9, @n8, @n7, @n6, @n5, @n4, @n3, @n2, @n1
UNION SELECT @n3, @n6, @n9, @n2, @n5, @n8, @n1, @n4, @n7
UNION SELECT @n3, @n2, @n1, @n7, @n6, @n5, @n9, @n8, @n7
UNION SELECT @n1, @n4, @n7, @n2, @n5, @n8, @n3, @n6, @n9
UNION SELECT @n7, @n8, @n9, @n4, @n5, @n6, @n1, @n2, @n3
UNION SELECT @n9, @n6, @n3, @n8, @n5, @n2, @n7, @n4, @n1;

This isn’t a really elegant solution as far as they go, and I’m sure someone smarter than me knows off-hand a nice way of handling the rotations and reflections better.

It does clock in at only 26ms though.  A full order of magnitude faster than the previous.

How’d you go? Can you think of a way to improve this further? Let me know!

 

1 thought on “SQL Puzzles – Magic Squares”

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 )

w

Connecting to %s