cube files
Indexed Cube Lovers Archive
A cubic graph with cubic diameter
Submitted by stannic on Mon, 03/06/2017 - 03:53.
The Fifteen puzzle is sometimes generalized to a sliding puzzle on an arbitrary simple connected graph G with n vertices in the following way.
As far as I can tell, 'the' reference on the solvability of such puzzles is Richard M. Wilson's 1974 paper [1], with Theorem 1 in the paper providing solvability conditions. (See also [4].)
A sliding puzzle on the following graph Gr on 10 vertices (Figure 1) is briefly discussed by Aaron F. Archer [2]. Archer uses the fact that Gr, like the underlying graph of the Fifteen puzzle, contains a hamiltonian path to show the Fifteen puzzle is solvable in half of all cases, while the puzzle on Gr is always solvable.
If my computations are correct, this particular sliding puzzle can be solved in at most 27 moves. Gr is a cubic graph (every vertex has degree 3), and
==================================================================================
* * * 1 * * * * * 2 * * * | Figure 2. The underlying
* * * * | graph of the 15 puzzle.
* * * * | -------------------------
* * * * * * 9 * * 3 * * * * * * |
* * * * * * | 1 * 2 * 3 * 4
* * * * * | * * * *
* * * * * * | 5 * 6 * 7 * 8
* * * * 8 * * 4 * * * * | * * * *
* * * * * * * * | 9 * 10 * 11 * 12
* * * * * * * * | * * * *
* * * * * 7 * * 6 * * 5 * * * * * | 13 * 14 * 15 * 0
* * * * * |
* * * * * | =========================
* * * * * * * * * * * * * * * * * * * * * | Figure 3. The exceptional
* * * | theta_0 graph from
* * * | R.M.Wilson's 1974 paper.
* * * * * * * * * * * * 0 * * * * * * * * * * * * | -------------------------
------------------------------------------------------ | 1 * * 2
Figure 1. A cubic graph. Edges 1-2, 2-3, ..., 8-9, 9-1 | * *
form a 9-cycle; the vertex 0 is adjacent to each of | * *
vertices 3, 6 and 9; edges 1-5, 2-7 and 4-8 are added, | 6 * * 0 * * 3
resulting in a graph with 10 vertices and 15 edges. | * *
Notice that there are two crossings; edges 0-6 and 4-8 | * *
intersect on the drawing, as well as edges 1-5 and 2-7.| 5 * * 4
==================================================================================
The graph Gr appears to be fairly well known; it is vertex-transitive and does not have a hamiltonian cycle, and it is mentioned in [3] as well.
In the sliding puzzle on Gr, there are 90 antipodes at distance 27 moves from the goal. This holds for any choice of the goal configuration, so 27 is actually the diameter of the graph whose vertices are configurations of the puzzle.
The number of configurations solvable in exactly d moves is given in Table 1 below; the table also provides symmetry-reduced counts. I believe these counts are correct; in particular, there are only 9 essentially distinct antipodes when the symmetries of Gr are accounted for (3 sets of 6 equivalent antipodes, and 6 sets of 12 equivalent antipodes, summing to
It seemed reasonable to also consider other graphs mentioned in the literature in connection to the Fifteen puzzle, so I brute-forced the 'exceptional' θ0 graph from [1] (Figure 3) as well. (This puzzle is also discussed in [3].) Three essentially different goal configurations are possible on θ0 (the possibilities can be distinguished by the number of degree-3 vertices adjacent to the unoccupied vertex). According to my program, each of these three possibilities yields exactly one antipode at distance 29. Thus God's numbers of sliding puzzles on these two graphs are few moves less than the God's number of the 3x3 version of the Fifteen puzzle (the latter is either 30 or 31 single-tile moves, depending on the choice of the goal configuration).
========================================== ======================= Table 1. The sliding puzzle on Gr (Fig. 1) The goal configuration ------------------------------------------ ( 0 1 2 3 4 5 6 7 8 9 ) without reduction with reduction ----------------------- d states total d states total Representatives of 9 ------------------------------------------ equivalence classes 0 1 1 0 1 1 of antipodes 1 3 4 1 1 2 ( 0 2 1 5 9 8 7 6 3 4 ) 2 6 10 2 1 3 ( 0 2 1 8 7 6 5 9 3 4 ) 3 12 22 3 1 4 ( 0 2 1 9 8 6 7 5 4 3 ) 4 24 46 4 2 6 ( 1 3 9 6 5 4 8 0 7 2 ) 5 48 94 5 4 10 ( 1 3 9 8 0 2 7 6 4 5 ) 6 96 190 6 8 18 ( 3 0 6 9 8 7 2 1 4 5 ) 7 192 382 7 16 34 ( 3 0 8 9 5 4 2 1 6 7 ) 8 384 766 8 32 66 ( 3 2 1 0 5 4 7 6 9 8 ) 9 768 1534 9 64 130 ( 3 7 9 0 6 8 2 5 1 4 ) 10 1530 3064 10 128 258 ======================= 11 3048 6112 11 255 513 12 5982 12094 12 500 1013 13 11736 23830 13 980 1993 14 23028 46858 14 1922 3915 15 44328 91186 15 3701 7616 16 83436 174622 16 6968 14584 17 151383 326005 17 12636 27220 18 261825 587830 18 21847 49067 19 420684 1008514 19 35097 84164 20 612508 1621022 20 51101 135265 21 749334 2370356 21 62527 197792 22 687500 3057856 22 57398 255190 23 413247 3471103 23 34538 289728 24 136811 3607914 24 11477 301205 25 19527 3627441 25 1674 302879 26 1269 3628710 26 118 302997 27 90 3628800 27 9 303006 ==========================================
B MacKenzie proposed a way to model the Fifteen puzzle as a group, by allowing the blank to 'jump' between opposite sides of the 4x4 box and representing the configuration relative to the position of the blank. The position of the blank itself is encoded by two 4-cycles. I wonder whether a similar construction is possible for the sliding puzzle on Gr.
Jaap Scherphuis has a page on his site discussing rotational puzzles on graphs. Gr has many cycles of the same length, so I modified the code to treat the graph as a rotary puzzle. There are cycles of lengths 5, 6, 8 and 9, so at least four different puzzles are possible, one puzzle for each cycle length. For each of these four puzzles, two natural move metrics are analogous to QTM and FTM in the case of the Rubik's cube; in the present case, I named the more restrictive metric 'STM' (short turns) and the less restrictive metric 'LTM' (long turns). (As an example, the column 'LTM 6' provides counts for the rotary puzzle where a move consists in choosing in the graph any cycle of length 6 and performing any cyclic permutation of the six pieces along the chosen cycle.)
==========================================================================
Table 2. Rotational puzzles on Gr: two move metrics, four cycle lengths
--------------------------------------------------------------------------
d STM 5 LTM 5 STM 6 LTM 6 STM 8 LTM 8 STM 9 LTM 9
--------------------------------------------------------------------------
0 1 1 1 1 1 1 1 1
1 24 48 20 50 30 105 40 140
2 528 2016 380 1835 870 8534 1560 13959
3 10888 75280 6970 57370 23620 483686 57650 794130
4 176969 1264305 117124 1082114 473544 3122630 1159868 1006170
5 1206750 472720 1130070 2454682 1781287 13844 595281 -
6 419210 30 1696135 32748 1339985 - - -
7 30 - 677340 - 9463 - - -
8 - - 760 - - - - -
--------------------------------------------------------------------------
1814400 1814400 3628800 3628800 3628800 3628800 1814400 1814400
==========================================================================
Assuming small graphs mentioned in the literature on sliding puzzles are solved, the question is where to go next. For example, it might be feasible to brute-force all simple non-separable graphs which are not polygons (i.e. the 'interesting' case [1]) on at most 9 vertices on a desktop computer in a week or two (each graph will generally yield between 1 and 9 nonequivalent sliding puzzles), and perhaps graphs with 10 vertices might be possible as well; however, it is unclear to me what to do with the results of such a batch computation; e.g. there seems to be no simple way to present it, as many different classes of graphs with different properties are mixed together. I thought it is more reasonable to pick a relatively small subclass of the 'interesting' case with more-or-less uniform properties.
Consider graph puz(G) (the notation follows [1]) with vertices corresponding to the configurations of a sliding puzzle on G. Edges of puz(G) correspond to possible moves from one configuration into another.
Given an arbitrary simple connected graph G, if G is a polygon, i.e. a graph with n vertices and n edges where each vertex has exactly two incident edges, a simple description exists of properties of puz(G) in terms of properties of G. If G is a polygon, puz(G) is a polygon too, since exactly two moves are possible in any configuration. Given n ≥ 3, the sliding puzzle with (n − 1) distinct pieces on G has n (n − 1) solvable configurations and there is exactly one antipode at distance 1/2 n (n − 1). (An example is the 2x2 version of the Fifteen puzzle. Its underlying graph is the square, and there are 12 solvable configurations and exactly one antipode at distance 6 moves.)
Cubic graphs are graphs with exactly three edges incident to every vertex. The graph Gr on Figure 1 has 10 vertices and 15 edges, and it can be seen it is indeed cubic. As a consequence, there are exactly three moves in every configuration of the puzzle, and exactly three edges are incident to every vertex in puz(Gr). (Thus puz(Gr) is the 'cubic graph with cubic diameter' mentioned in the title of this post; the diameter of Gr itself is 2.)
According to OEIS, there are 19 connected cubic graphs on 10 vertices. One of those 19 graphs is separable (it consists of two identical parts joined by a single edge) and it turns out only 5760 out of
=========================================== 4 6 8 10 12 14 16 18 20 n (the number of vertices) ------------------------------------------- 1 2 5 19 85 509 4060 41301 510489 connected cubic graphs (OEIS A002851) - - - 1 4 29 186 1435 12671 - separable - 1 1 2 5 13 38 149 703 - non-separable bipartite 1 1 4 16 76 467 3836 39717 497115 - non-separable with an odd cycle ===========================================
The separable connected cubic graph on 10 vertices yields three inequivalent sliding puzzles. The God's number is the same (20 moves) for all three puzzles, but the number of antipodes differs (18, 27 or 30 antipodes).
Out of 2 non-separable bipartite cubic graphs on 10 vertices, one is a Möbius ladder and yields only one sliding puzzle, with God's number 30 and 3 antipodes. The second graph from this subset is described below.
================================================================================ A B Take three copies of the 6-vertex 5-edge graph H on the left. Vertices * * labeled A, B, E, F are shared between all three copies of H, but each C * D copy of H has its own copy of C and its own copy of D. The result * * is a bipartite cubic graph with 10 vertices and 15 edges; each of two E F sliding puzzles on this graph has 2 antipodes at distance 35 moves. ================================================================================
Out of the 16 non-separable non-bipartite cubic graphs on 10 vertices, the graph Gr shown on the Figure 1 yields a puzzle with God's number 27, which is the lowest possible God's number for a sliding puzzle on a non-separable cubic graph on 10 vertices. Another graph (resembling the underlying graph of the 5x2 version of the Fifteen puzzle) yields three inequivalent puzzles, including the following one with God's number 48 (which is the highest possible God's number for this particular set of graphs, according to my solver).
===================================================================================== 1 * 2 * 3 * 4 * 5 A puzzle with God's number 48 and 2 antipodes. The underlying * X * X * graph can be obtained from the 5x2 grid graph by deleting two 6 * 7 * 8 * 9 * 0 edges (2-7 and 4-9) and adding four edges (1-7, 2-6, 4-0, 5-9). =====================================================================================
Further details: I downloaded connected cubic graphs on 10 vertices from this page. Later I managed to generate this set myself to make sure my copy of the file was not corrupted and there were no errors during conversion.
For completeness, here is the distance distribution for the graph Gr itself. There are 6 'antipode' vertices at the maximum distance 2 from any chosen initial vertex.
============== d count total 0 1 1 1 3 4 2 6 10 ==============
References
- [1] Richard M. Wilson, "Graph puzzles, homotopy, and the alternating group" J. Combin. Theory Ser. B 16 (1974) 86-96.
- [2] Aaron F. Archer, "A Modern Treatment of the 15 Puzzle" Mathematical Monthly 106 (1999) 793-799.
- [3] Alex Fink, Richard Guy, "Rick's Tricky Six Puzzle: S5 Sits Specially in S6" Mathematics Magazine Vol 80, No. 2, April 2009, pp. 83-102.
- [4] Alexander Bogomolny, Puzzles on graphs (Cut The Knot)
