/ 
Graph-Maker-Other-8
River stage zero No dependents
/ 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 in size order, smallest at the top. Each graph vertex is a configuration of discs on spindles. Each 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, and if those two other spindles are not empty then the smaller disc of them 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 legal moves 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 different 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. For discs=>3 above these are vertices 0, 13 and 26. These are degree 2 and other vertices are degree 3. The puzzle is to traverse from one such all-discs corner to another. There's many ways to do that but the shortest is 2^N-1 moves along the side shown.

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 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 as 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 taking advantage of the extra places, 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 of disconnected pairs since only the smallest disc can ever move.

Spindles 3,4,5 appears 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 around digits 0 to S-1, so digit changes are +/-1 mod S.

For spindles<=3 cyclic is the same as adjacency "any". For spindles>=4 some moves between spindles are disallowed when cyclic, so is 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 yet here 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 digit changes +/-1 in the middle or +1 or -1 at the ends.

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 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 change 0<->1 (different centre). 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

discs=2, https://hog.grinvin.org/ViewGraphInfo.action?id=21136
discs=2, linear, https://hog.grinvin.org/ViewGraphInfo.action?id=414 (path-9)
discs=3, https://hog.grinvin.org/ViewGraphInfo.action?id=22740
discs=2, spindles=4, https://hog.grinvin.org/ViewGraphInfo.action?id=22742
discs=2, spindles=4, cyclic, https://hog.grinvin.org/ViewGraphInfo.action?id=25141
discs=2, spindles=4, linear, https://hog.grinvin.org/ViewGraphInfo.action?id=25143
discs=2, spindles=4, star, https://hog.grinvin.org/ViewGraphInfo.action?id=21152

SEE ALSO

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

LICENSE

Copyright 2015, 2016, 2017 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/.