This is the first in what I hope will be a semi-regular series of recreational puzzles where SQL can be used to find the answer. I set these puzzles on occasional Fridays in my workplace, and as I now have quite an archive I thought I should start sharing them with a wider audience.
I came up with the idea for this puzzle involving Magic Squares by accident while trying to do something different – and getting it wrong! For a moment I thought I’d had an original idea but then it was “Hang on – I’m sure I must have seen this before.”
A bit of googling and that thought was proved right – I’m just not that original. In fact the first documented instance of these appears to be the Chinese legend of Lo Shu – possibly dating back as far as 650BC. I was only beaten by the best part of three millennia…
You may have seen these before at some point – but hopefully long enough ago that you don’t know all the answers! Possibly like me they ring a bell for you but you can’t remember exactly where from.
A Magic Square is a square grid e.g. 1×1, 2×2, 3×4, 4×4…. or n x n, where numbers are placed in each square in the grid such that if you add up the numbers in each column, row, or diagonally they all add up to the same total.
Usually you use consecutive numbers starting from 1 (placing each number just once), so in the 2 x 2 grid you would place the numbers 1 to 4, in the 3 x 3 the numbers 1 to 9 – and so on.
Here’s the 1 x1 grid:
I thought I’d be generous and give you that one for free 😉
So my first question is can you find a solution (with the numbers 1 to 4) to the 2 x 2 grid:
Having explored that possibility (not for too long I hope!) the meat of this puzzle is to find solutions to the 3 x 3 grid using the numbers 1 to 9:
In fact, using SQL, can you not just find one solution, but all the possible solutions? How many are there?
Share your attempts and answers in the comments.
Have fun 🙂
Attempt – 1
declare @num int = 3
declare @count int = 1
declare @count1 int = 1
declare @num1 int = @num
declare @values varchar(8000) = ”
declare @str varchar(500) = ‘create table ##tmpdata( ‘
while @count <= @num
begin
select @str = @str + 'col' + cast(@count as varchar) + ' int, '
select @values = @values + '('
while @count1 <= @num1
begin
select @values = @values + cast(@count1 as varchar) + ','
select @count1 = @count1 + 1
end
select @values = left(@values, len(@values)-1) + '),'
select @num1 = @num1 + @num
set @count = @count + 1
end
select @str = left(@str, len(@str)-1) + ')'
select @values = left(@values, len(@values)-1)
print @str
print 'insert into ##tmpdata values '+ @values
exec (@str)
exec('insert into ##tmpdata values '+ @values)
select * from ##tmpdata
drop table ##tmpdata
Hey Grover. You might find it easier to start with a fixed grid of 3×3 rather than trying to do it for a grid of size @num. Then you can create a table that will hold all the possible combinations of the numbers 1 to 9, then test which make a magic square.
Hello,
Thanks for feedback. I am sorry that I could not understand reply. Could you please explain. But the code that I posted works for any number like 5,4,10. Just pass it through @num. I mean it can be converted into a sproc.
Hi Grover – it works to generate and populate the table, but it doesn’t find a magic square – was suggesting you may need a different data format to be able to test lots of permutations of the grid to be able to find the “Magic” ones, but I may be misunderstanding your approach so go for it if you feel this is the way. Regards 🙂
Hi Matthew,
I misunderstood the requirement and that is “where numbers are placed in each square in the grid such that if you add up the numbers in each column, row, or diagonally they all add up to the same total”. I will work on this.. 😊
Here’s my solution which prints out the 8 possible magic squares (all rotations and reflections of a single answer):
Declare @d1 int
Declare @d2 int
Declare @d3 int
Declare @d4 int
Declare @d5 int
Declare @d6 int
Declare @d7 int
Declare @d8 int
Declare @d9 int
Declare @i int = 123456789
Declare @j int
Declare @k int
While @i < 987654322
Begin
— Print @i
Set @k = @i
Set @j = 100000000
Set @d1 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d2 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d3 = @k / @j
If @d1 + @d2 + @d3 15
Begin
Set @i = @i + 1000000
Continue
End
Set @k = @k % @j
Set @j = @j / 10
Set @d4 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d5 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d6 = @k / @j
If @d4 + @d5 + @d6 15
Begin
Set @i = @i + 1000
Continue
End
Set @k = @k % @j
Set @j = @j / 10
Set @d7 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d8 = @k / @j
Set @d9 = @k % @j
Set @i = @i + 1 — do it now so continue can be used
If @d7 + @d8 + @d9 15 Continue
— Test cols
If @d1 + @d4 + @d7 15 Continue
If @d2 + @d5 + @d8 15 Continue
If @d3 + @d6 + @d9 15 Continue
— Test diags
If @d1 + @d5 + @d9 15 Continue
If @d3 + @d5 + @d7 15 Continue
— all digits used
If @d1 * @d2 * @d3 * @d4 * @d5 * @d6 * @d7 * @d8 * @d9 362880 Continue
— Success
Print Cast(@d1 AS char(1)) + N’ ‘ + Cast(@d2 AS char(1)) + N’ ‘ + Cast(@d3 AS char(1))
Print Cast(@d4 AS char(1)) + N’ ‘ + Cast(@d5 AS char(1)) + N’ ‘ + Cast(@d6 AS char(1))
Print Cast(@d7 AS char(1)) + N’ ‘ + Cast(@d8 AS char(1)) + N’ ‘ + Cast(@d9 AS char(1))
Print N’—–‘
End
Hi Mark – I mostly get the idea of your approach, but something seems to have gone wrong with the paste into the comments box, seem to be missing = signs or != signs or something. If you check and re-send I’ll try it out. Cheers, Matthew.
Hope this is clearer.
~~~~
Declare @d1 int
Declare @d2 int
Declare @d3 int
Declare @d4 int
Declare @d5 int
Declare @d6 int
Declare @d7 int
Declare @d8 int
Declare @d9 int
Declare @i int = 123456789
Declare @j int
Declare @k int
While @i < 987654322
Begin
— Print @i
Set @k = @i
Set @j = 100000000
Set @d1 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d2 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d3 = @k / @j
If @d1 + @d2 + @d3 15
Begin
Set @i = @i + 1000000
Continue
End
Set @k = @k % @j
Set @j = @j / 10
Set @d4 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d5 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d6 = @k / @j
If @d4 + @d5 + @d6 15
Begin
Set @i = @i + 1000
Continue
End
Set @k = @k % @j
Set @j = @j / 10
Set @d7 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d8 = @k / @j
Set @d9 = @k % @j
Set @i = @i + 1 — do it now so continue can be used
If @d7 + @d8 + @d9 15 Continue
— Test cols
If @d1 + @d4 + @d7 15 Continue
If @d2 + @d5 + @d8 15 Continue
If @d3 + @d6 + @d9 15 Continue
— Test diags
If @d1 + @d5 + @d9 15 Continue
If @d3 + @d5 + @d7 15 Continue
— all digits used
If @d1 * @d2 * @d3 * @d4 * @d5 * @d6 * @d7 * @d8 * @d9 362880 Continue
— Success
Print Cast(@d1 AS char(1)) + N’ ‘ + Cast(@d2 AS char(1)) + N’ ‘ + Cast(@d3 AS char(1))
Print Cast(@d4 AS char(1)) + N’ ‘ + Cast(@d5 AS char(1)) + N’ ‘ + Cast(@d6 AS char(1))
Print Cast(@d7 AS char(1)) + N’ ‘ + Cast(@d8 AS char(1)) + N’ ‘ + Cast(@d9 AS char(1))
Print N’—–‘
End
~~~~
No that failed too. I don’t know how to stop your comment processor from messing with my code. I know it works, but it does take 27 seconds on my PC.
I’ll look into the comments issue, standard wordpress so not sure how much I can change. Good to know it takes 27 seconds, be interesting to see if people can beat that!
I had a quick look and WordPress seems to use Markdown and markdown suggested that surrounding the code with ~~~~ ~~~~ would do the trick but it didn’t. I’ve never used Markdown so I am not familiar with it, so it’s probably my fault.
Another look at Mardown and it should work with spaces at the start of each line, so, if at first …
Declare @d1 int
Declare @d2 int
Declare @d3 int
Declare @d4 int
Declare @d5 int
Declare @d6 int
Declare @d7 int
Declare @d8 int
Declare @d9 int
Declare @i int = 123456789
Declare @j int
Declare @k int
While @i < 987654322
Begin
— Print @i
Set @k = @i
Set @j = 100000000
Set @d1 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d2 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d3 = @k / @j
If @d1 + @d2 + @d3 15
Begin
Set @i = @i + 1000000
Continue
End
Set @k = @k % @j
Set @j = @j / 10
Set @d4 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d5 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d6 = @k / @j
If @d4 + @d5 + @d6 15
Begin
Set @i = @i + 1000
Continue
End
Set @k = @k % @j
Set @j = @j / 10
Set @d7 = @k / @j
Set @k = @k % @j
Set @j = @j / 10
Set @d8 = @k / @j
Set @d9 = @k % @j
Set @i = @i + 1 — do it now so continue can be used
If @d7 + @d8 + @d9 15 Continue
— Test cols
If @d1 + @d4 + @d7 15 Continue
If @d2 + @d5 + @d8 15 Continue
If @d3 + @d6 + @d9 15 Continue
— Test diags
If @d1 + @d5 + @d9 15 Continue
If @d3 + @d5 + @d7 15 Continue
— all digits used
If @d1 * @d2 * @d3 * @d4 * @d5 * @d6 * @d7 * @d8 * @d9 362880 Continue
— Success
Print Cast(@d1 AS char(1)) + N’ ‘ + Cast(@d2 AS char(1)) + N’ ‘ + Cast(@d3 AS char(1))
Print Cast(@d4 AS char(1)) + N’ ‘ + Cast(@d5 AS char(1)) + N’ ‘ + Cast(@d6 AS char(1))
Print Cast(@d7 AS char(1)) + N’ ‘ + Cast(@d8 AS char(1)) + N’ ‘ + Cast(@d9 AS char(1))
Print N’—–‘
End
No – it’s still taken out the not equals signs. I should have used != instead.
Hi Matt,
Stumbled on this last night. My solution is listed here: http://www.databythebeach.com/puzzle-time/
Have a look!
Hi Matt. I must be misunderstanding the puzzle here because I do not see any solution to the 2×2 puzzle. Hopefully I am not missing something obvious!
The question was “can you find any solutions to the 2×2 puzzle” – the correct answer is – No, there are no possible solutions (possibly a bit of a trick question!)
Ha ha … okay thanks for clarifying!
My solution uses a nice method of finding a solutions of odd sized magic squares:
/*
Script Author: Gerard Kroon
Date 2017-11-29
Script purpose: This script generates valid Magic Square, applicable for any odd sized Magic Square
Here only size 3×3 is explored
Alternative you can loop over the 9! =1*2*3*4*5*6*7*8*9 = 362880 possible permutations of 123456789
to find the ones which add up according to the definition of a magic square
*/
IF object_id(‘tempdb.dbo.#magicsquare’,’U’) IS NOT NULL DROP TABLE #magicsquare;
CREATE TABLE #magicsquare
(
r0c2 INT
,r1c1 INT, r1c2 INT, r1c3 INT
,r2c0 INT ,r2c1 INT, r2c2 INT, r2c3 INT, r2c4 INT
,r3c1 INT, r3c2 INT, r3c3 INT,
r4c2 INT
)
/*
start with 1 2 3
4 5 6
7 8 9
and rotate this 45 degrees to the right to get (the 0-cells are actualy empty cells)
1
4 0 2
7 0 5 0 3
8 0 6
9
or, mirrored result from
3 2 1
6 5 4
9 8 7
rorated to the left
1
2 0 4
3 0 5 0 7
6 0 8
9
*/
/*
— for a quick one solution, start with the first pattern,
— and update the empty cells (the zeros) with the number in the opposite outside cells
INSERT INTO #magicsquare VALUES (1,2,null,4,3,null,5,null,7,6,null,8,9)
UPDATE #magicsquare SET r1c2=r4c2, r2c1=r2c4,r2c3=r2c0,r3c2=r0c2,r0c2=null,r2c0=null,r2c4=null,r4c2=null
SELECT * from #magicsquare
*/
/*
rotate this square over 45 degrees to the right around the center r2,c2:
r1c1->r0c2, r1c2->r1c3, r1c3->r2c4,
r2c1->r1c1, r2c2->r2c2, r2c3->r3c3,
r3c1->r2c0, r3c2->r3c1, r3c3->r4c2
now 4 cells are empty in the square: r1c2, r2c1, r2c3 and r3c2
fill these with the number from the opposite cells outside the square:
r0c2->r3c2,
r2c0->r2c3, r2c4->r2c1,
r4c2->r1c2
*/
DECLARE @i AS INT = 1 — inner loop from 1..8
, @j AS INT = 1 — outer loop from 1..2 for mirrorred starting position
DECLARE
@r0c2 INT
,@r1c1 INT, @r1c2 INT, @r1c3 INT
,@r2c0 INT ,@r2c1 INT, @r2c2 INT, @r2c3 INT ,@r2c4 INT
,@r3c1 INT, @r3c2 INT, @r3c3 INT
, @r4c2 INT
WHILE @j<=2
BEGIN
IF @j=1
BEGIN
— start with original square 1,2,3; 4,5,6; 7,8,9
SET @r0c2 = null
; SET @r1c1 = 1; SET @r1c2 = 2; SET @r1c3 = 3
; SET @r2c0 = null
; SET @r2c1 = 4; SET @r2c2 = 5; SET @r2c3 = 6
; SET @r2c4 = null
; SET @r3c1 = 7; SET @r3c2 = 8; SET @r3c3 = 9
; SET @r4c2 = null
END
ELSE
BEGIN
— repeat with mirrored starting square
SET @r0c2 = null
; SET @r1c1 = 3; SET @r1c2 = 2; SET @r1c3 = 1
; SET @r2c0 = null
; SET @r2c1 = 6; SET @r2c2 = 5; SET @r2c3 = 4
; SET @r2c4 = null
; SET @r3c1 = 9; SET @r3c2 = 8; SET @r3c3 = 7
; SET @r4c2 = null
END
— rotate 8 times to the right over 45 degrees for 4 different solutions
WHILE @i<=8
BEGIN;
–fill the #magicsquare with the current values, outside cells are null
–but only every second rotation, after a rotation of 90 degrees when the number 1 is outside
IF @i%2=0
INSERT INTO #magicsquare VALUES (
@r0c2
,@r1c1, @r1c2, @r1c3
,@r2c0 ,@r2c1, @r2c2, @r2c3 ,@r2c4
,@r3c1, @r3c2, @r3c3
, @r4c2
)
;
–rotate this square over 45 degrees to the right around the center r2c2
–considering the order of assignments as not use overwritten values
SET @r0c2=@r1c1;
SET @r2c0=@r3c1; SET @r2c4=@r1c3;
SET @r1c1=@r2c1; SET @r1c3=@r1c2;
–SET @r2c2=@r2c2; — center does not move
SET @r4c2=@r3c3;
SET @r3c1=@r3c2; SET @r3c3=@r2c3;
–not needed for the computer, only for human:
–SET @r1c2=null; SET @r2c1=null; SET @r2c3=null; SET @r3c2=null
— now insert outside numbers in opposite cells
SET @r3c2=@r0c2;
SET @r2c3=@r2c0;
SET @r2c1=@r2c4;
SET @r1c2=@r4c2;
SET @i = @i + 1;
END;
SET @j = @j + 1;
SET @i = 1;
END;
— now humans come to see:
UPDATE #magicsquare SET r0c2=null,r2c0=null,r2c4=null,r4c2=null
— all the solutions:
SELECT * FROM #magicsquare
— validate:
SELECT r1c1+r1c2+r1c3 as SumRow1
, r2c1+r2c2+r2c3 as SumRow2
, r3c1+r3c2+r3c3 as SumRow3
, r1c1+r2c1+r3c1 as SumCol1
, r1c2+r2c2+r3c2 as SumCol2
, r1c3+r2c3+r3c3 as SumCol3
, r1c1+r2c2+r3c3 as SumDiag1
, r1c3+r2c2+r3c1 as SumDiag2
FROM #magicsquare
Because the tabs are deleted in the post upload, you have a less readable layout now
Yep, the comments functionality on my blog is pretty poor for code, unfortunately requires me to shift platform to fix so that may be a way off!
This will work in SQL Server and returns the correct results.
It’s more of a set based approach that the others here, runs in about 5 seconds on my local machine.
The assigns letters to each position in the square, generates all unique combinations then filters down to the ones that meet the requirements.
Position letter assignments:
A B C
D E F
G H I
————————————————————————
begin tran
drop table #Numbers
————————————————————————
— Generate a numbers table.
————————————————————————
;with GetNumbers as (
select number = 1
union all select 2
union all select 3
union all select 4
union all select 5
union all select 6
union all select 7
union all select 8
union all select 9
)
select *
into #Numbers
from GetNumbers
————————————————————————
— This is ugly but it works. There’s a better way to
— populate the table but I’d have to think about it more.
————————————————————————
select
a = a.number
,b = b.number
,c = c.number
,d = d.number
,e = e.number
,f = f.number
,g = g.number
,h = h.number
,i = i.number
into #allCombos
from #Numbers a
join #Numbers b on a.number != b.number
join #Numbers c on b.number != c.number and a.number != c.number
join #Numbers d on c.number != d.number and b.number != d.number and a.number != d.number
join #Numbers e on d.number != e.number and c.number != e.number and b.number != e.number and a.number != e.number
join #Numbers f on e.number != f.number and d.number != f.number and c.number != f.number and b.number != f.number and a.number != f.number
join #Numbers g on f.number != g.number and e.number != g.number and d.number != g.number and c.number != g.number and b.number != g.number and a.number != g.number
join #Numbers h on g.number != h.number and f.number != h.number and e.number != h.number and d.number != h.number and c.number != h.number and b.number != h.number and a.number != h.number
join #Numbers i on h.number != i.number and g.number != i.number and f.number != i.number and e.number != i.number and d.number != i.number and c.number != i.number and b.number != i.number and a.number != i.number
order by
a.number
,b.number
,c.number
,d.number
,e.number
,f.number
,g.number
,h.number
,i.number
————————————————————————
— Grab records that match
————————————————————————
select *
from #allCombos
where
a+b+c = a+d+g
and a+d+g = a+e+i
and a+e+i = c+f+i
and c+f+i = b+e+h
and b+e+h = g+h+i
and g+h+i = d+e+f
and d+e+f = g+e+c
rollback tran
Hey Matthew,
If I’m doing this wrong – feel free to let me know 🙂 Like John, I just stumbled across the latest and went back to 1.
I think I must be doing something wrong though, because my solution is 230ms on my pc.
DECLARE @nums TABLE(n TINYINT)
INSERT INTO @nums (n)
VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9)
SELECT n1, n2, n3, n4, n5, n6, n7, n8, n9
FROM (
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,
n1.n + n2.n + n3.n row1,
n4.n + n5.n + n6.n row2,
n7.n + n8.n + n9.n row3,
n1.n + n4.n + n7.n col1,
n2.n + n5.n + n8.n col2,
n3.n + n6.n + n9.n col3,
n1.n + n5.n + n9.n diag1,
n3.n + n5.n + n7.n diag2
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)
) t
WHERE row1 = row2 AND row2 = row3 AND row1 = col1
AND col1 = col2 AND col2 = col3
AND row1 = diag1 AND diag1 = diag2
You actually make it seem really easy with your presentation however I find this topic to be actually one thing that I believe I might never understand. It kind of feels too complicated and very large for me. I am taking a look forward on your next publish, I will try to get the hold of it!
It’s actually a nice and useful piece of information. I am happy that you simply shared this useful information with us. Please stay us informed like this. Thanks for sharing.