The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Graph-Maker-Other-19
River stage zero No dependents
1 ++
/ Graph::Maker::Hanoi

NAME

Graph::Maker::Hanoi - create towers of Hanoi puzzle graph

SYNOPSIS

 use Graph::Maker::Hanoi;
 $graph = Graph::Maker->new ('hanoi', discs => 3);

DESCRIPTION

Graph::Maker::Hanoi creates a Graph.pm graph of configurations occurring in the towers of Hanoi puzzle. This is equivalent to points of the Sierpinski triangle and the odd numbers in Pascal's triangle.

      0  discs=>0         0                     0
                         / \  discs=>2         / \    discs=>3
                        1---2                 1---2
      0  discs=>1      /     \               /     \
     / \              7       5             7       5
    1---2            / \     / \           / \     / \
                    8---6---3---4         8---6---3---4
                                         /             \
                                       17              22
                                       / \             / \
                                     15--16          23--21
                                     /     \         /     \
                                   12      10      20      24
                                   / \     / \     / \     / \
                                 13--14--11---9--18--19--25--26

The Hanoi puzzle has N discs and 3 spindles. The discs on a spindle are stacked in size order, smallest at the top. A legal move takes the top disc from one spindle and puts it on another, but a a bigger disc may not go on top of a smaller disc.

Each graph vertex is a configuration of discs on spindles. Each graph edge is a legal move from one configuration to another.

There are either two or three legal moves. The smallest disc can always move to either of the other two spindles. Unless those spindles are both empty, the smaller of the top discs can move to the other.

Vertex names are integers 0 to 3^N-1. Each ternary digit is a disc and its value 0,1,2 is which spindle holds that disc. The least significant digit is the smallest disc. The edges are then to change the least significant digit to either of its two other values. Or skip the low run of the least significant digit and at the first non-L digit (if there is one) change it to the third value (not itself and not the least significant).

    ........ L  -> L+1,L+2 mod 3
    ...M L L L  -> M+1 or M+2 mod 3, whichever is not L

The case of no digit M different from L is 00..00, 11..11 and 22..22 which are all discs on a single spindle. In discs=>3 drawn above, these are vertices 0, 13 and 26. They are degree 2 and other vertices are degree 3. The puzzle is to traverse from one degree=2 all-discs corner to another. There's many ways to do that but the shortest is 2^N-1 moves along the side.

The Hanoi graph is Hamiltonian (has a cycle visiting every vertex exactly once) by traversing each third in the style of the Sierpinski arrowhead (eg. Math::PlanePath::SierpinskiArrowheadCentres). In discs=>3 drawn above, the Hamiltonian cycle is an arrowhead traversal 4 to 8, then likewise 17 to 9, and 18 to 22.

Spindles

Option spindles => S specifies how many spindles are used for the puzzle. The default is 3 described above. For S spindles and N discs, the vertices are numbered 0 to S^N-1 inclusive and each digit in base S is which spindle holds the disc. An edge is a change of digit at a position p provided that neither old nor new digit appears in any of the positions below p (as that would mean a smaller disc on the source or destination spindle).

Discs=1 is always a complete-S since the single disc can move from anywhere to anywhere.

Discs >= 2 has complete-S sub-graphs which are the small disc moving around on some configuration of the bigger discs. Connections between those subgraphs are moves of the bigger discs, where permitted.

The puzzle is again to move all discs from one spindle to another. Spindles >= 4 can be done in fewer moves than spindles=3 by using the extra spindles(s), but the problem of a shortest path is more difficult. In spindles=3, the biggest disc can only move by putting all smaller discs on the other spindle, but for >=4 there are many ways to distribute the smaller discs on the other spindles.

Spindles=1 is allowed but is a trivial 1-vertex graph since all discs are on that spindle and no moves are possible.

Spindles=2 is allowed but is 2^N vertices in pairs since only the smallest disc can ever move.

Spindles = 3,4,5 appear as "The Reve's Puzzle" in

    "The Canterbury Puzzles and Other Curious Problems", Henry Ernest Dudeney, 1907

Dudeney gives minimum move solutions for spindles=4 when discs are triangular numbers 1,3,6,10,etc, and for spindles=5 when discs are triangular pyramid numbers 1,4,10,20,etc.

Cyclic

Option adjacency => "cyclic" treats the spindles as a cycle where discs can only move forward or backward to adjacent spindles in the cycle. In the vertex digit representation, the cycle is digits 0 to S-1, so a move (when permitted) is a digit changes are +/-1 with wrap-around mod S, and so an edge subset of a cyclic grid graph of S dimensions and width N discs.

For spindles<=3, cyclic is the same as adjacency "any". For spindles>=4, some moves between spindles are disallowed when cyclic, so an edge subset of adjacency "any".

(This option is for cyclic with moves in either direction. Another possibility is cyclic with moves only in one direction around the cycle, as considered by Scorer, Grundy and Smith. There's nothing here yet for a directed graph of this kind.)

Linear

Option adjacency => "linear" treats the spindles as a row and discs can only move forward or backward between consecutive spindles in the row. This is a form given for 4 spindles in

In the vertex digit representation, the row is digits 0 to S-1, so a move (when permitted) is a digit change +/-1 with no wrap-around, and so an edge subset of a grid graph of S dimensions and width N discs.

The puzzle is to move all discs from the first spindle to the last, which means a path from vertex 0 to S^N-1.

For spindles<=2, linear is the same as "any". For spindles>=3 some moves between spindles are disallowed when linear, so an edge subset of cyclic, which in turn is an edge subset of any.

            edges
    ---------------------
    any = cyclic = linear       for spindles <= 2
    any = cyclic > linear       for spindles = 3
    any > cyclic > linear       for spindles >= 4

Star

Option adjacency => "star" has one centre spindle and discs can move only between that centre and another spindle (no moves among the other spindles). This is a form given for 4 spindles in

In the vertex digit representation, digit 0 is the centre.

For spindles<=2, star is the same as "any". For spindles=3 star is equivalent to linear above but with digit flip 0<->1 (the centre is different). For spindles>=4, star is an edge subset of adjacency "any".

FUNCTIONS

$graph = Graph::Maker->new('hanoi', key => value, ...)

The key/value parameters are

    discs     =>  integer
    spindles  =>  integer, default 3
    adjacency =>  string, default "any"
    graph_maker => subr(key=>value) constructor, default Graph->new

adjacency can be

    "any"        any moves between spindles permitted
    "cyclic"     moves only between spindles in a cycle
    "linear"     moves only between spindles in a row
    "star"       moves only to or from centre spindle

Other parameters are passed to the constructor, either graph_maker or Graph->new().

If the graph is directed (the default) then edges are added both forward and backward between vertices. Option undirected => 1 creates an undirected graph and for it there is a single edge between vertices.

HOUSE OF GRAPHS

House of Graphs entries for graphs here include

    spindles=3 (default)
      discs=0             1310  (singleton)
      discs=1             1374  (triangle)
      discs=1, linear    32234  (path-3)

      discs=2            21136
      discs=2, linear      414  (path-9)

      discs=3            22740
      discs=4            35479
      discs=5            35481

      (For 3 spindles, cyclic=any and star=linear.)

    spindles=4
      discs=0             1310  (singleton)
      discs=1               74  (complete-4)
      discs=1, linear      594  (path-4)

      discs=2            22742
      discs=2, cyclic    25141
      discs=2, linear    25143
      discs=2, star      21152

    spindles=5
      discs=0             1310  (singleton)
      discs=1              462  (complete-5)
      discs=1, linear      286  (path-5)

      discs=2            44075
      discs=2, linear    44071

    spindles=6
      discs=0             1310  (singleton)
      discs=1              232  (complete-6)
      discs=1, linear      568  (path-6)
      discs=2, linear    44073

SEE ALSO

Graph::Maker, Graph::Maker::HanoiExchange, Graph::Maker::Complete, Graph::Maker::Cycle, Graph::Maker::Linear

HOME PAGE

http://user42.tuxfamily.org/graph-maker-other/index.html

LICENSE

Copyright 2015, 2016, 2017, 2018, 2019, 2020, 2021 Kevin Ryde

This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.