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!

 

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