# Towers of Hanoi

Towers of Hanoi

Works with PostgreSQL

>=8.4

Written in

SQL

Depends on

Nothing

```-- auxiliary function for towers of hanoi
-- select the next state for a given move for a given stick

create or replace function hnext (move int, ndiscs int,
this int[], right int[], left int[])
returns int[]
language sql as
\$\$
select
case when \$1 % 2 = 1 then
-- on odd numbered moves move smallest disc,
-- clockwise if ndiscs is odd, counterclockwise if it's even
case when 1 = any(\$3) then
\$3[array_lower(\$3,1):array_upper(\$3,1)-1]
when \$2 %2 = 1 and 1 = any(\$5) then
\$3 || 1
when \$2 %2 = 0 and 1 = any(\$4) then
\$3 || 1
else \$3
end
else
-- on even numbered moves, make the only other move possible
case when 1 = any(\$3) then
\$3
when 1 = any(\$5) then
case when array_length(\$3,1) = 1 then
\$3 || \$4[array_upper(\$4,1)]
when array_length(\$4,1) = 1 then
\$3[array_lower(\$3,1):array_upper(\$3,1)-1]
when \$3[array_upper(\$3,1)] < \$4[array_upper(\$4,1)] then
\$3[array_lower(\$3,1):array_upper(\$3,1)-1]
else
\$3 || \$4[array_upper(\$4,1)]
end
else
case when array_length(\$3,1) = 1 then
\$3 || \$5[array_upper(\$5,1)]
when array_length(\$5,1) = 1 then
\$3[array_lower(\$3,1):array_upper(\$3,1)-1]
when \$3[array_upper(\$3,1)] < \$5[array_upper(\$5,1)] then
\$3[array_lower(\$3,1):array_upper(\$3,1)-1]
else
\$3|| \$5[array_upper(\$5,1)]
end
end
end
\$\$;

-- main function
-- recursively calculate the next state from the present state

create or replace function hanoi
(discs integer, move out integer, a out int[], b out int[], c out int[])
returns setof record
language sql as
\$\$
with recursive han as (
select 1::int as move, \$1 as ndiscs,
'{99}'::int[] || array_agg(discs)as a,
'{99}'::int[] as b, '{99}'::int[] as c
from generate_series(\$1,1,-1) as discs
union all
select move + 1 , ndiscs,
hnext(move, ndiscs, a,b,c),
hnext(move, ndiscs, b,c,a),
hnext(move, ndiscs, c,a,b)
from han
where array_length(b,1) < ndiscs + 1
)
select move, a[2:\$1+1] as a, b[2:\$1+1] as b, c[2:\$1+1] as c
from han
order by move
\$\$;

-- see all the states, use a small number here
select * from hanoi(5);

-- count the states, can use larger numbers here
select count(*) from hanoi(16);
```

--Adunstan 14:20, 21 November 2009 (UTC)