/ 
Graph-Maker-Other-19
/ Graph::Maker::HanoiSwitching

NAME

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

SYNOPSIS

use Graph::Maker::HanoiSwitching;
$graph = Graph::Maker->new ('hanoi_switching', 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 a stack of discs switches with the next bigger disc.

Sandi Klavzar, Uros Milutinovic, "Graphs S(n,k) and a Variant of the Tower of Hanoi Problem",

0---3--12--15       discs => 2
| X |   | X |       spindles => 4
1---2  13--14
|     X     |       where each X is
4---7   8--11       edges crossing
| X |   | X |
5---6---9--10

The puzzle has N discs and S 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 move, which in the variation here is

  • Stack 1..k-1 on top of one spindle switches places with disc k on top of another spindle. Disc k=1 is the smallest and can switch with an empty stack (so moves freely).

Klavzar and Milutinovic show that for S=3 spindles the resulting graph is isomorphic to the plain Hanoi graph.

Moves of the smallest disc are complete-S subgraphs. They are cross connected at a different vertex each, which is where a N-1 discs is on one spindle. In the illustration above, the complete 0..3 cross connects 1-4, 2-8, 3-12. For S=3, further connections are from 5,10,15 to copies of the S=2 graph.

Vertices are integers 0 to S^N-1 inclusive and each digit in base S is which spindle 0..S-1 holds the disc. The least significant digit is the smallest disc. The edges are then to change the least significant digit to another value; or the run of low digits equal to the least significant switches values with the next higher digit (the lowest not equal to the least significant).

      high      low
from   2 1 0 2 2 2
to     2 1 2 0 0 0
           \-----/

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

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 a path of 2^N vertices, by alternately moving the smallest or switching. This is consecutive 0 to 2^N-1,

00000    spindles => 2, in binary
00001
00010    alternately move smallest and switch low run 1s
00011
00100
...

FUNCTIONS

$graph = Graph::Maker->new('hanoi_switching', 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.

HOUSE OF GRAPHS

House of Graphs entries for graphs here include

https://hog.grinvin.org/ViewGraphInfo.action?id=21136 (etc)

spindles=3 (default)
  same as Hanoi

spindles=4
  discs=0             1310  singleton
  discs=1               74  complete-4

SEE ALSO

Graph::Maker, Graph::Maker::Hanoi, Graph::Maker::HanoiExchange, 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/.