More “Magic Squares” Solutions

Another thought occured to me tonight while I was phased out and not doing much of note.  There is another assumption I can add in to my solution of Matthew McGiffen’s Magic Squares Puzzle that I blogged about yesterday.

  • We have the set of numbers – 1 to 9.
  • We know it has to fit a grid of 3×3.
  • We know the columns and rows and diagonals must equal.
  • Therefore, we know each row is 1/3rd of 1 + 2 + 3 + 4 … + 9.
  • Each row sums up to 15.

Now we already have the math setting up to ensure the rows and columns and diagonals all equal in the previous solution – but we can also add a predicate to the JOINs to ensure that the numbers joined into each row are never greater than 15.

This will reduce the number of JOINs and the number of rows that ever get selected to be filtered.

It also means that I don’t need the ugly UNION code from the previous example.  It is slightly slower in at around 45ms – almost double the more performant solution – but I like the way it fits together.

DECLARE @nums TABLE(n TINYINT)
DECLARE @third TINYINT

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

SELECT @third = SUM(n) / 3.0 FROM @nums

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 AND n1.n + n2.n <= @third
   JOIN @nums n3 ON n3.n NOT IN (n1.n, n2.n) AND n1.n + n2.n + n3.n = @third
   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) AND n4.n + n5.n <= @third
   JOIN @nums n6 ON n6.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n) AND n4.n + n5.n + n6.n = @third
   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) AND n7.n + n8.n <= @third
   JOIN @nums n9 ON n9.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n) AND n7.n + n8.n + n9.n = @third
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);

And now that I have typed that out…

Would you believe between 2 – 4ms?  Seriously.  I can’t.

DECLARE @nums TABLE(n TINYINT)
DECLARE @third 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 @third = SUM(n) / 3.0 FROM @nums

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 AND n1.n + n2.n <= @third
    JOIN @nums n3 ON n3.n NOT IN (n1.n, n2.n) AND n1.n + n2.n + n3.n = @third
    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) AND n4.n + n5.n <= @third
    JOIN @nums n6 ON n6.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n) AND n4.n + n5.n + n6.n = @third
    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) AND n7.n + n8.n <= @third
    JOIN @nums n9 ON n9.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n) AND n7.n + n8.n + n9.n = @third
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; 

I mentioned in the last blog post that with that brute forcing through the numbers in the JOINS gets us to the 21,814th row, and then we have 8 rotations and reflections?

Obviously, with the JOINs in this solution, the only rows that will get returned are those where the three rows add up to 15.  This returns 2,592 rows, the 179th of which matches our criteria.

So, from that test I can only surmise one thing.  I can make this even faster.  I just need to move the logic of my testing from the WHERE clause to the JOIN clauses.

This one takes around 15ms and only returns the 8 rows that match the logic we’re after.

DECLARE @nums TABLE(n TINYINT)
DECLARE @third TINYINT

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

SELECT @third = SUM(n) / 3.0 FROM @nums

SELECT n1.n, n2.n, n3.n,
       n4.n, n5.n, n6.n,
       n7.n, n8.n, n9.n
FROM @nums n1
     JOIN @nums n2 ON n2.n <> n1.n
         AND n1.n + n2.n < @third -- ROW 1 < 15
     JOIN @nums n3 ON n3.n NOT IN (n1.n, n2.n)
         AND n1.n + n2.n + n3.n = @third -- ROW 1 = 15
     JOIN @nums n4 ON n4.n NOT IN (n1.n, n2.n, n3.n)
         AND n1.n + n4.n < @third -- COL 1 < 15
     JOIN @nums n5 ON n5.n NOT IN (n1.n, n2.n, n3.n, n4.n)
         AND n4.n + n5.n < @third -- ROW 2 < 15
         AND n2.n + n5.n < @third -- COL 2 < 15
         AND n1.n + n5.n < @third -- DIAG 1 < 15
         AND n3.n + n5.n < @third -- DIAG 2 < 15
     JOIN @nums n6 ON n6.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n)
         AND n4.n + n5.n + n6.n = @third -- ROW 2 = 15
         AND n3.n + n6.n < @third -- COL 3 < 15
     JOIN @nums n7 ON n7.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n)
         AND n1.n + n4.n + n7.n = @third -- COL 1 = 15
         AND n3.n + n5.n + n7.n = @third -- DIAG 2 = 15
     JOIN @nums n8 ON n8.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n)
         AND n7.n + n8.n < @third -- ROW 3 < 15
         AND n2.n + n5.n + n8.n = @third -- COL 2 = 15
     JOIN @nums n9 ON n9.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n)
         AND n7.n + n8.n + n9.n = @third -- ROW 3 = 15
         AND n3.n + n6.n + n9.n = @third -- COL 3 = 15
         AND n1.n + n5.n + n9.n = @third -- DIAG 1 = 15

And if I shortcut that one to only get the first result of matching numbers, then perform the “manual” reflections and rotations?

I’m getting a total of 0 – 1ms in my execution, once it’s in the query plan cache.  Sometimes I execute and it’s zero, and sometimes I have a total of 1ms in execution time, with 0 CPU time mentioned.

DECLARE @nums TABLE(n TINYINT)
DECLARE @third 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 @third = SUM(n) / 3.0 FROM @nums

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
        AND n1.n + n2.n < @third -- ROW 1 < 15
     JOIN @nums n3 ON n3.n NOT IN (n1.n, n2.n)
        AND n1.n + n2.n + n3.n = @third -- ROW 1 = 15
     JOIN @nums n4 ON n4.n NOT IN (n1.n, n2.n, n3.n)
        AND n1.n + n4.n < @third -- COL 1 < 15
     JOIN @nums n5 ON n5.n NOT IN (n1.n, n2.n, n3.n, n4.n)
        AND n4.n + n5.n < @third -- ROW 2 < 15
        AND n2.n + n5.n < @third -- COL 2 < 15
        AND n1.n + n5.n < @third -- DIAG 1 < 15
        AND n3.n + n5.n < @third -- DIAG 2 < 15
     JOIN @nums n6 ON n6.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n)
        AND n4.n + n5.n + n6.n = @third -- ROW 2 = 15 
        AND n3.n + n6.n < @third -- COL 3 < 15
     JOIN @nums n7 ON n7.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n)
        AND n1.n + n4.n + n7.n = @third -- COL 1 = 15
        AND n3.n + n5.n + n7.n = @third -- DIAG 2 = 15
     JOIN @nums n8 ON n8.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n)
        AND n7.n + n8.n < @third -- ROW 3 < 15 
        AND n2.n + n5.n + n8.n = @third -- COL 2 = 15
     JOIN @nums n9 ON n9.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n)
        AND n7.n + n8.n + n9.n = @third -- ROW 3 = 15
        AND n3.n + n6.n + n9.n = @third -- COL 3 = 15
        AND n1.n + n5.n + n9.n = @third; -- DIAG 1 = 15

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;

 

And now, I think it’s time to don the ole straight jacket and hop into my padded cell for the night.

You know, when I posted yesterday I was quite happy with the two solutions.  I thought it was quite a good attempt – getting from a > 10 minute loop-based SQL query down to 250ms and then taking it down to a further 26ms was great for me.  I would have left it there.

And then my brain took a quiet moment, brought back the problem and thought of something I could optimise further.  Even though it took more time I preferred the solution.  And then, I just couldn’t leave it alone when I wondered about how that would go with my more performant solution… 2 – 4ms later and I knew I was onto something and I kept digging until I have something that is pretty much instant.

Seriously, if you can beat this one – let me know so I can buy you a beer! I pretty much think this is me calling it…  I am surprised how I thought I had a solution and how much improvement I could still wring from it today.  It goes to show you, there’s always another take on it. Later!

 

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!