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

NAME

Graph::Maker::HanoiExchange - create towers of Hanoi exchanging discs graph

SYNOPSIS

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

DESCRIPTION

Graph::Maker::Hanoi creates a Graph.pm graph of configurations of discs on spindles in a variation on the towers of Hanoi puzzle where pairs of discs exchange.

    R. S. Scorer, P. M. Grundy and C. A. B. Smith, "Some Binary Games", The Mathematical Gazette, July 1944, volume 28, number 280, pages 96-103, http://www.jstor.org/stable/3606393, section 4(iii) Plane Network Game.

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

The puzzle has N discs and 3 spindles. The discs on a spindle are stacked in size order, smallest at the top. Each graph vertex is a configuration of discs on spindles. Each graph edge is a legal step from one configuration to another. In the variation here, these are:

  • Smallest disc moves to any other spindle.

  • Two discs exchange when they differ in size by 1, are on different spindles, and each is top-most on its spindle.

A configuration has up to 4 possible steps (vertex degrees <= 4). The maximum is when the smallest, 2nd smallest, and 3rd smallest, are the tops of the 3 spindles. The smallest moves to 2 places, the smallest and 2nd exchange, and the 2nd and 3rd exchange. For example vertex 5 in the discs=3 example above.

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 another value; or exchange two adjacent digits provided neither occurs anywhere below its position (which also requires they're two different digit values).

For discs <= 1 the graph is the same as the plain Hanoi. For discs=2 the graph is isomorphic, but the vertex names are not the same. For discs >= 3 the graph is different from the plain Hanoi, essentially since cross connections between subgraphs are from inner-most points like 5--11 in the example above.

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.

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 exchanges (including exchanges of the smallest and second smallest).

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 path-4 subgraphs since only the smallest and 2nd smallest discs can ever move.

FUNCTIONS

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

The key/value parameters are

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

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.

FORMULAS

Solution Length and Diameter

The path length between corner vertices, which is the solution moving N discs from one spindle to another, is calculated and shown to be the graph diameter by

    Paul K. Stockmeyer et al, "Exchanging Disks in the Tower of Hanoi", International Journal of Computer Mathematics, volume 59, number 1-2, pages 37-47, 1995. http://www.cs.wm.edu/~pkstoc/gov.pdf. See f(n) in section 3.

as recurrence

    f(N) = f(N-1) + f(N-2) + 2*f(N-4) + 3    for N>=4
         = 0, 1, 3, 7, 13, 25, 47, 89, 165, ...

This grows as a power r^N where r = 1.853... is the largest root of x^4 - x^3 - x^2 - 2. (Smaller than the plain Hanoi 2^N - 1.)

They consider also the geometric distance in a layout such as drawn above. The resulting distance grows as 7/2*2^N.

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this tree include

    A341579    diameter

HOUSE OF GRAPHS

House of Graphs entries for graphs here include

    spindles=3 (default)
      discs=0        1310  singleton
      discs=1        1374  triangle
      discs=2       21136  same as plain Hanoi
      discs=3       44105
      discs=4       44107
      discs=5       44109

SEE ALSO

Graph::Maker, Graph::Maker::Hanoi, Graph::Maker::Complete

HOME PAGE

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

LICENSE

Copyright 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/.