SQL Puzzle 5: Prime Magic

Quite a few of you have read or attempted the previous puzzle SQL Puzzle 1: Magic Squares

As a quick reminder, when you have a 3 x 3 grid, a magic square is one where each row, column or diagonal add up to the same value. e.g.

magic-square

All the rows, all the columns and both diagonals each add up to 15.

In the previous puzzle I asked you to write SQL to find all the possible 3 x 3 magic squares. After originally coming across that idea I discovered all sorts of variants on the magic square theme.

This time, I’ll ask you to find write SQL to find just one 3 x 3 magic square, but in this case one composed only of prime numbers? They don’t have to be consecutive primes (though they do all have to be different), and to make things easier you can treat the number 1 as a prime if you want.

Have fun!

Previous Puzzles:
SQL Puzzle 1: Magic Squares
SQL Puzzle 2: Eight Queens
SQL Puzzle 3: Knights and Queens
SQL Puzzle 4: The Beale Papers

3 thoughts on “SQL Puzzle 5: Prime Magic

  1. Hey Matthew,

    So I left an answer on the Puzzle 1 today, and just ran the same answer for this against a group of primes. Because I’m lazy. Chopping it off at the lowest result that worked for me, gets me 5:09 on my machine. (CPU time = 307890 ms, elapsed time = 309035 ms.)

    Of course, if I limit it to just the 9 working numbers then it’s still 250ms. If I get bonus points for that 😉

    I’d hate to see a cursor/loop version of this one though!

    DECLARE @nums TABLE(n SMALLINT)

    INSERT INTO @nums (n)
    VALUES (1), (2), (3), (5), (7), (11), (13), (17), (19), (23), (29), (31), (37), (41), (43), (47), (53), (59), (61), (67), (71), (73)–, (79), (83), (89), (97), (101), (103), (107), (109), (113), (127), (131), (137), (139), (149), (151), (157), (163), (167), (173), (179), (181), (191), (193), (197), (199)

    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)

    Like

    1. And I realised on the way home where I could make this better, by taking the top 1 and using the numbers to get rotations and reflections.

      IE 1 … 73 comes up way faster than…
      ….
      ….
      ….
      5 minutes later…
      73 … 1

      I’ll have to post a follow up!

      Like

    2. Okay, I couldn’t wait. Here it is, on a much older/slower laptop.

      CPU time = 10875 ms, elapsed time = 10908 ms.
      CPU time = 234 ms, elapsed time = 241 ms.

      Just over 11 seconds all up. Not bad down from 5m 09s.

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

      INSERT INTO @nums (n)
      VALUES (1), (2), (3), (5), (7), (11), (13), (17), (19), (23), (29), (31), (37), (41), (43), (47), (53), (59), (61), (67), (71), (73)–, (79), (83), (89), (97), (101), (103), (107), (109), (113), (127), (131), (137), (139),
      (149), (151), (157), (163), (167), (173), (179), (181), (191), (193), (197), (199)

      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)

      INSERT INTO @filterednums (n)
      VALUES (@n1), (@n2), (@n3), (@n4), (@n5), (@n6), (@n7), (@n8), (@n9)

      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 @filterednums n1
      JOIN @filterednums n2 ON n2.n n1.n
      JOIN @filterednums n3 ON n3.n NOT IN (n1.n, n2.n)
      JOIN @filterednums n4 ON n4.n NOT IN (n1.n, n2.n, n3.n)
      JOIN @filterednums n5 ON n5.n NOT IN (n1.n, n2.n, n3.n, n4.n)
      JOIN @filterednums n6 ON n6.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n)
      JOIN @filterednums n7 ON n7.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n)
      JOIN @filterednums n8 ON n8.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n)
      JOIN @filterednums 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)

      Like

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