Towers of Hanoi

-- 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);