The Towers of Hanoi are a classic children’s puzzle. With 3 pegs and a set of disks of differing sizes, the goal is to move a stack of disks (arranged with largest on the bottom to smallest on top) from one peg to another moving only one disk at a time, never putting a larger disk on top of a smaller disk.
A trivial version is a stack of 2 disks: one small, one large. Move the small disk to one of the empty pegs. Then move the large disk to the other empty peg; and finally move the small disk on top of the large disk. Thus the stack has moved and the puzzle is solved.
With 3 disks it becomes a more involved as more steps are required.
STEP A B C Description 0 123 starting position 1 23 1 move disk 1 to peg B 2 3 1 2 move disk 2 to peg C 3 3 12 move disk 1 to peg C 4 3 12 move disk 3 to peg B 5 1 3 2 move disk 1 to peg A 6 1 23 move disk 2 to peg B 7 123 move disk 1 to peg B - done
The minimum number of steps required to move a stack of N disks will be 2N-1. So, as the number of disks increases, the number of steps needed grows rapidly.
While the number of steps increases, the method of solving the puzzle does not increase in difficulty. The first move will always be moving the small disk. In my examples, I’ll always move it one peg to the right and when I get to peg C, I’ll wrap around to peg A. It would be wasteful to move the same piece twice, so I’ll grab a new disk. Assuming I don’t move the same disk twice, there will only ever be one disk available to move after moving the small disk. That might not be immediately obvious, but we can see it in the 3-disk example above. In step 2, after moving disk-1, The only disk available is disk-2. so I move it to the only peg available. Then I move disk-1 again. At this point there is only 1 disk available and that is disk-3, which I move. Then I move disk-1 again.
At this point I have all 3 disks spread out. At first it might seem like I could move anything but, if I stick to not repeating a disk then I can’t move disk-1 again. I also can’t move disk-3 because moving it would place it on top of a smaller disk. Thus, the only disk available is disk-2. I move it, and then go back to disk-1 again to complete the puzzle.
No matter how many disks are in the puzzle or how many intermediate steps have been taken, after moving disk-1 (the smallest disk) there will only ever be one disk you can move and it will only have one possible destination.
So, using this knowledge, it would be fairly easy to write some procedural code to iterate these steps either directly or recursively; but as this article title suggests, the goal here isn’t to use PL/SQL.
Can we solve the Towers of Hanoi with just plain old SQL? This wouldn’t be much of an article if the answer was no, so the answer then is YES!
Before jumping straight to the solution, I’ll break down the steps I used to write it. As the method above indicates there are essentially just 2 steps. Either I move the small disk, or I move one other disk which must be the only legal move. I always start with the small disk and then alternate. So, odd-numbered moves are always moving the small disk. Even-numbered moves are moving a different disk.
I’ll use a recursive sql query to generate my moves. Since I know an optimal solution will always take 2N-1 moves I can use that rule to define an ending to my move counter.
WITH
hanoi (step, a, b, c)
AS
(SELECT 0, '123', '', '' FROM DUAL
UNION ALL
SELECT step + 1, a, b, c
FROM hanoi
WHERE step < POWER(2, LENGTH(a || b || c)) - 1)
SELECT *
FROM hanoi;
STEP A B C
---- --- - -
0 123
1 123
2 123
3 123
4 123
5 123
6 123
7 123
Checking for odd vs even steps is a little counter-intuitive. Since the “step” value coming in to the recursive portion of the query is from the prior row, I look for odd steps by checking if the prior step value was even.
WITH
hanoi (step, a, b, c)
AS
(SELECT 0, '123', '', '' FROM DUAL
UNION ALL
SELECT step + 1,
CASE -- on odd moves, move the smallest piece
-- on even moves, move the only legal piece
-- that isn't the smallest piece
WHEN MOD(step, 2) = 0 THEN 'ODD'
ELSE 'EVEN'
END,
b,
c
FROM hanoi
WHERE step < POWER(2, LENGTH(a || b || c)) - 1)
SELECT *
FROM hanoi;
STEP A B C
---- ---- - -
0 123
1 ODD
2 EVEN
3 ODD
4 EVEN
5 ODD
6 EVEN
7 ODD
Now that I have my odd/even determined for each step I can start adding the rules for moving a disk from each peg. Each either has the small disk (“1”) on top, in which case that disk will move away from that peg; or, the disk might receive the disk. I’m using a simplistic algorithm where the small disk always moves to the right, in a circle. So A->B, B->C, C->A.
So, for each peg I check if it has the small-disk. If so, I remove it (LTRIM because it will always be first, i.e. on top.) If that’s not the case I check if that peg’s feeder has the small-disk. If so, then put that disk on top of this peg by concatenating it to the front (top) of this peg’s list. If neither of those cases are true, then this peg doesn’t change so return it’s current stack. Now my query looks like this…
WITH
hanoi (step, a, b, c)
AS
(SELECT 0, '123', '', '' FROM DUAL
UNION ALL
SELECT step + 1,
CASE
-- on odd moves, move the smallest piece
-- on even moves, move the only legal piece
-- that isn't the smallest piece
WHEN MOD(step, 2) = 0
THEN
CASE
WHEN a LIKE '1%' THEN LTRIM(a, '1')
WHEN c LIKE '1%' THEN '1' || a
ELSE a
END
END,
CASE
WHEN MOD(step, 2) = 0
THEN
CASE
WHEN b LIKE '1%' THEN LTRIM(b, '1')
WHEN a LIKE '1%' THEN '1' || b
ELSE b
END
END
b,
CASE
WHEN MOD(step, 2) = 0
THEN
CASE
WHEN c LIKE '1%' THEN LTRIM(c, '1')
WHEN b LIKE '1%' THEN '1' || c
ELSE c
END
END
c
FROM hanoi
WHERE step < POWER(2, LENGTH(a || b || c)) - 1)
SELECT *
FROM hanoi;
If the step is even, the conditions are little trickier. Unlike the odd steps which have a known disk with a fixed movement rule, the even steps vary each time on which peg holds the legal disk and which peg is the legal destination. So for each peg there will be a block like this:
CASE
WHEN x LIKE '1%'
THEN
x
WHEN y NOT LIKE '1%' AND (x IS NULL OR y < x)
THEN
SUBSTR(y, 1, 1) || x
WHEN z NOT LIKE '1%' AND (x IS NULL OR z < x)
THEN
SUBSTR(z, 1, 1) || x
ELSE
SUBSTR(x, 2)
END
x is the current peg and I check if it holds the small disk (x LIKE ‘1%’) if so, then I’m not going to move it again nor will move another disk on top of it so I return this peg as is.
Then I check both of the other pegs (y and z), if x does not have the small disk then one of the others must. If either has the small disk it won’t be used. If a non-small disk is found, I compare to see if it is smaller than the top disk on our current peg. Since the strings are stacks which are always sorted, I can simply compare the strings directly to check the first characters. If y or z has a smaller disk than x on top then we can move the disk from that peg to this peg. We can also do that if the current peg is empty.
The last case (ELSE) is this peg has the disk which will be moved. In this case we remove the top disk from this peg (i.e. remove the first character of the string.)
Each peg will have a similar structure in the query but the x, y, and z columns will vary. Thus the new query is…
WITH
hanoi (step, a, b, c)
AS
(SELECT 0, '123', '', '' FROM DUAL
UNION ALL
SELECT step + 1,
CASE
-- on odd moves, move the smallest piece
-- on even moves, move the only legal piece
-- that isn't the smallest piece
WHEN MOD(step, 2) = 0
THEN
CASE
WHEN a LIKE '1%' THEN LTRIM(a, '1')
WHEN c LIKE '1%' THEN '1' || a
ELSE a
END
WHEN a LIKE '1%'
THEN
a
WHEN c NOT LIKE '1%' AND (a IS NULL OR c < a)
THEN
SUBSTR(c, 1, 1) || a
WHEN b NOT LIKE '1%' AND (a IS NULL OR b < a)
THEN
SUBSTR(b, 1, 1) || a
ELSE
SUBSTR(a, 2)
END,
CASE
WHEN MOD(step, 2) = 0
THEN
CASE
WHEN b LIKE '1%' THEN LTRIM(b, '1')
WHEN a LIKE '1%' THEN '1' || b
ELSE b
END
WHEN b LIKE '1%'
THEN
b
WHEN a NOT LIKE '1%' AND (b IS NULL OR a < b)
THEN
SUBSTR(a, 1, 1) || b
WHEN c NOT LIKE '1%' AND (b IS NULL OR c < b)
THEN
SUBSTR(c, 1, 1) || b
ELSE
SUBSTR(b, 2)
END,
CASE
WHEN MOD(step, 2) = 0
THEN
CASE
WHEN c LIKE '1%' THEN LTRIM(c, '1')
WHEN b LIKE '1%' THEN '1' || c
ELSE c
END
WHEN c LIKE '1%'
THEN
c
WHEN b NOT LIKE '1%' AND (c IS NULL OR b < c)
THEN
SUBSTR(b, 1, 1) || c
WHEN a NOT LIKE '1%' AND (c IS NULL OR a < c)
THEN
SUBSTR(a, 1, 1) || c
ELSE
SUBSTR(c, 2)
END
FROM hanoi
WHERE step < POWER(2, LENGTH(a || b || c)) - 1)
SELECT *
FROM hanoi;
But – if you try this query you will likely get an error. I tried it on 19c and 21c databases. Including Oracle’s own livesql.oracle.com, which as of this writing is Live SQL 21.4.1, running Oracle Database 19c Enterprise Edition – 19.8.0.0.0.
On livesql it simply says “Internal Server Error.” Running it locally I get ORA-03113: end-of-file on communication channel. The problem appears to be in the data types. As a workaround I pull the initial values into separate WITH clause and then CAST the values to VARCHAR2 inside the hanoi sub-query. Once all of the strings are VARCHAR2 the query works as intended.
WITH
initialize (a, b, c) AS(SELECT '123', '', '' FROM DUAL),
hanoi (step, a, b, c)
AS
(SELECT 0,
CAST(a AS VARCHAR2(35)),
CAST(b AS VARCHAR2(35)),
CAST(c AS VARCHAR2(35))
FROM initialize
UNION ALL
SELECT step + 1,
CASE
-- on odd moves, move the smallest piece
-- on even moves, move the only legal piece
-- that isn't the smallest piece
WHEN MOD(step, 2) = 0
THEN
CASE
WHEN a LIKE '1%' THEN LTRIM(a, '1')
WHEN c LIKE '1%' THEN '1' || a
ELSE a
END
WHEN a LIKE '1%'
THEN
a
WHEN c NOT LIKE '1%' AND (a IS NULL OR c < a)
THEN
SUBSTR(c, 1, 1) || a
WHEN b NOT LIKE '1%' AND (a IS NULL OR b < a)
THEN
SUBSTR(b, 1, 1) || a
ELSE
SUBSTR(a, 2)
END,
CASE
WHEN MOD(step, 2) = 0
THEN
CASE
WHEN b LIKE '1%' THEN LTRIM(b, '1')
WHEN a LIKE '1%' THEN '1' || b
ELSE b
END
WHEN b LIKE '1%'
THEN
b
WHEN a NOT LIKE '1%' AND (b IS NULL OR a < b)
THEN
SUBSTR(a, 1, 1) || b
WHEN c NOT LIKE '1%' AND (b IS NULL OR c < b)
THEN
SUBSTR(c, 1, 1) || b
ELSE
SUBSTR(b, 2)
END,
CASE
WHEN MOD(step, 2) = 0
THEN
CASE
WHEN c LIKE '1%' THEN LTRIM(c, '1')
WHEN b LIKE '1%' THEN '1' || c
ELSE c
END
WHEN c LIKE '1%'
THEN
c
WHEN b NOT LIKE '1%' AND (c IS NULL OR b < c)
THEN
SUBSTR(b, 1, 1) || c
WHEN a NOT LIKE '1%' AND (c IS NULL OR a < c)
THEN
SUBSTR(a, 1, 1) || c
ELSE
SUBSTR(c, 2)
END
FROM hanoi
WHERE step < POWER(2, LENGTH(a || b || c)) - 1)
SELECT *
FROM hanoi;
STEP A B C
0 123
1 23 1
2 3 1 2
3 3 12
4 3 12
5 1 3 2
6 1 23
7 123
In these examples I only used digits but this is extensible to stacks larger than 9. With the query written as above, you must have ‘1’ be the small disk; but you can use any characters that collate larger than that. I’ve tested up to stacks of 22 disks using numbers and letters. On my pc it took about 85 seconds to generate the 4,194,303 steps needed to solve the puzzle with this initalizer:
initialize (a, b, c) AS(SELECT '123456789ABCDEFGHIJKLM', '', '' FROM DUAL),
This was a fun puzzle to tackle in SQL. When I first thought of it, I thought it might be a lot more convoluted. But breaking each step down and iterating for each peg it ended up being fairly straight forward. The hardest part of it ended up being the data type errors which caused me to spend a lot trying to find logic bugs that weren’t there. At first I assumed my problems were somewhere in runaway recursion. Once I convinced myself the logic was sound I started looking for odd edge cases in syntax that might produce errors and eventually found the data types were a culprit.
Thanks for reading. Questions and comments, as always, are welcome.
Hi Sean,
Another piece of SQL art 🙂
Amazing, as always 🙂
Thanks a lot for sharing and enjoy a happy holidays season 🙂
Cheers & Best Reagrds,
Iudith