A cubic graph with cubic diameter

The Fifteen puzzle is sometimes generalized to a sliding puzzle on an arbitrary simple connected graph G with n vertices in the following way. n − 1 movable pieces numbered 1, 2, ... (n − 1) are placed on vertices of the graph G. At most one piece is placed on each vertex. One vertex of G is left unoccupied. A move consists in choosing a vertex v adjacent to the currently unoccupied vertex v0 and 'sliding' the piece at v along the edge (v; v0). The aim is to restore the order so that piece numbered i occupies vertex numbered i, for i = 1 .. n − 1. In the case of the Fifteen Puzzle, the underlying graph G is the 4 × 4 grid graph, and a degree-2 vertex is left unoccupied in the goal configuration.

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 27 = 33 is a cube, so I figured out this has to be related to the Rubik's cube in some way.

==================================================================================
               * * * 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 3 × 6 + 6 × 12 = 90); also, there are 303,006 essentially different configurations, of which 1176 have at least one symmetry. However, an independent confirmation would be appreciated; when doing symmetry reduction, I did make several errors (hopefully fixed now) which did not surface at all in the case of the Fifteen Puzzle.

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 10! = 3,628,800 configurations are reachable in any sliding puzzle on that graph. Two other graphs from this set are non-separable and bipartite; by R. M. Wilson's theorem, 10! / 2 configurations are solvable in any sliding puzzle on any of those two graphs. The remaining 16 graphs are non-separable and have an odd cycle, thus all configurations are solvable in any sliding puzzle on any of those 16 graphs.

===========================================
  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)

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Modelling the sliding puzzle on Gr as a group

I wonder whether a similar construction is possible for the sliding puzzle on Gr.

After several attempts to extend the approach of B MacKenzie, I believe I constructed a permutation group with 3 generators and 2 * 10! elements, exactly 2 elements for each configuration of the sliding puzzle on Gr. I show my solution below with GAP code. (I do not claim it is an example of a 'good' GAP code. I have little experience with GAP and did not formally study group theory, so there are probably ways to improve the code, both in terms of style and in terms of performance.)

gap) L := (3,4,5,6)(1,7,9,2,8)(10,13,14,15,16)(11,17,19,12,18);;
gap) R := (3,6,5,4)(1,8,2,9,7)(10,16,15,14,13)(11,18,12,19,17);;
gap) V := (10,19)(1,3,8,6)(2,4,7,5)(11,13,18,16)(12,14,17,15);;
gap) L * R; V^4; V^2;
()
()
(1,8)(2,7)(3,6)(4,5)(11,18)(12,17)(13,16)(14,15)
gap) L * V^2 = V^2 * R;
true
gap) G := Group(L, V);; Size(G); Factorial(10) * 2;
7257600
7257600

The generators are L, R and V, with L * R = V^4 = 1 and L * V^2 = V^2 * R. These generators permute both the 'tiles' (sliding pieces) and the vertices of the graph. The pieces 1 through 9 are encoded as 1 through 9 respectively; the vertices 0 through 9 are encoded as 10 through 19 respectively. Note that the 'empty piece' is not affected by any of the generators (in fact, the generators are chosen so that the 'empty piece' is fixed) and thus is not encoded at all.

Elements g and V^2 * g belong to the same equivalence class EqClass(g) (that is, represent the same configuration of the sliding puzzle):

EqClass := function(g)
    return Set([ g, V^2 * g ]);
end;

Each equivalence class contains 2 elements:

EqClass(V^2 * g) = { V^2 * g, V^4 * g } = { V^2 * g, g } = EqClass(g).

To be able to perform breadth-first search, I defined a function Expand which accepts a 2-element equivalence class ec:

Expand := function(ec)
    local rep, left, right, vert;
    rep := ec[1];
    left  := EqClass(L * rep);
    right := EqClass(R * rep);
    vert  := EqClass(V * rep);
    return Set([ left, right, vert ]);
end;

The set of three equivalence classes returned by Expand does not depend on the particular choice of rep in the body of the function. Indeed, if rep = g, then

left  = EqClass(L * g),
right = EqClass(R * g),
vert  = EqClass(V * g);

if rep = V^2 * g, then

left  = EqClass(L * V^2 * g) = { L * V^2 * g, V^2 * L * V^2 * g } = { V^2 * R * g, R * g } = EqClass(R * g),
right = EqClass(R * V^2 * g) = { R * V^2 * g, V^2 * R * V^2 * g } = { V^2 * L * g, L * g } = EqClass(L * g),
vert  = EqClass(V * V^2 * g) = { V * V^2 * g, V^2 * V * V^2 * g } = { V^3 * g, V * g }     = EqClass(V * g).

My implementation of breadth-first search in GAP is: (edited with a faster implementation)

Bfs := function(layer0, expand_func)
    local prev_layer, curr_layer, next_layer, ec;
    prev_layer := Set([]); curr_layer := Set(layer0);
    while Length(curr_layer) > 0 do
        Print(" ", Length(curr_layer), "\c");
        next_layer := List([]);
        for ec in curr_layer do Append(next_layer, expand_func(ec)); od;
        next_layer := Set(next_layer);
        SubtractSet(next_layer, prev_layer);
        SubtractSet(next_layer, curr_layer);
        prev_layer := curr_layer; curr_layer := next_layer;
    od;
end;

The goal configuration of the sliding puzzle corresponds to the equivalence class of the identity permutation. Running the code in GAP 4.8.6 produces the following output after ~6 minutes (peak memory usage is ~600 MB):

gap) goal := EqClass( () );
[ (), (1,8)(2,7)(3,6)(4,5)(11,18)(12,17)(13,16)(14,15) ]
gap) Bfs( [ goal ], Expand );
 1 3 6 12 24 48 96 192 384 768 1530 3048 5982 11736 23028 44328 83436
 151383 261825 420684 612508 749334 687500 413247 136811 19527 1269 90

Replacing the goal with a random configuration yields the same counts:

gap) Bfs( [ EqClass(Random(G)) ], Expand );
 1 3 6 12 24 48 96 192 384 768 1530 3048 5982 11736

I could not find a similar construction with Size(G) = Factorial(10) (i.e. with elements of a group G in one-to-one correspondence to configurations of the sliding puzzle on the graph Gr), and it may be the case that there is no such construction. I guess a proof might use the fact that Gr is not a Cayley graph, but I could not yet understand how to proceed further.

A javascript simulator

I wrote a minimal simulator in javascript for the sliding puzzle on the graph Gr from the original post. The simulator uses <canvas> and should (I hope) work on most modern browsers.

Connected cubic graphs with ≤ 10 vertices

Below are listed all connected cubic graphs with at most 10 vertices.

============================================================================================================================
 n id | d g aut  wi |                                                       edges | gn.antipodes                      states
============================================================================================================================
 4  1 | 1 3  24   6 |                                     0-1,0-2,0-3,1-2,1-3,2-3 | 4.5                                   24
============================================================================================================================
 6  1 | 2 4  72  21 |                         0-1,0-2,0-3,1-4,1-5,2-4,2-5,3-4,3-5 | 10.4                                 360

 6  2 | 2 3  12  21 |                         0-1,0-2,0-3,1-2,1-4,2-5,3-4,3-5,4-5 | 13.1                                 720
============================================================================================================================
 8  1 | 3 4  48  48 |             0-1,0-2,0-3,1-4,1-5,2-4,2-6,3-5,3-6,4-7,5-7,6-7 | 19.18                              20160
 
 8  2 | 2 4  16  44 |             0-1,0-2,0-3,1-4,1-5,2-4,2-6,3-5,3-7,4-7,5-6,6-7 | 20.6                               40320
 8  3 | 2 3  12  44 |             0-1,0-2,0-3,1-2,1-4,2-5,3-6,3-7,4-6,4-7,5-6,5-7 | 22.2,21.24,21.29                   40320
 8  4 | 3 3   4  46 |             0-1,0-2,0-3,1-2,1-4,2-5,3-4,3-6,4-7,5-6,5-7,6-7 | 25.1,25.1,25.1                     40320
 8  5 | 3 3  16  50 |             0-1,0-2,0-3,1-2,1-3,2-4,3-5,4-6,4-7,5-6,5-7,6-7 | 34.2,34.2                          40320
============================================================================================================================
10  1 | 5 3  32 111 | 0-1,0-2,0-3,1-2,1-3,2-4,3-4,4-5,5-6,5-7,6-8,6-9,7-8,7-9,8-9 | 20.30,20.18,20.27                   5760

10  2 | 3 4  20  85 | 0-1,0-2,0-3,1-4,1-5,2-4,2-6,3-5,3-7,4-8,5-9,6-8,6-9,7-8,7-9 | 30.3                             1814400
10  3 | 3 4  48  85 | 0-1,0-2,0-3,1-4,1-5,2-4,2-5,3-6,3-7,4-8,5-9,6-8,6-9,7-8,7-9 | 35.2,35.2                        1814400

10  4 | 2 5 120  75 | 0-1,0-2,0-3,1-4,1-5,2-6,2-7,3-8,3-9,4-6,4-8,5-7,5-9,6-9,7-8 | 27.90                            3628800
10  5 | 3 4   4  81 | 0-1,0-2,0-3,1-4,1-5,2-4,2-6,3-5,3-7,4-8,5-9,6-7,6-9,7-8,8-9 | 29.18,29.7,29.12                 3628800
10  6 | 3 4  20  85 | 0-1,0-2,0-3,1-4,1-5,2-4,2-6,3-5,3-7,4-8,5-9,6-7,6-8,7-9,8-9 | 30.13                            3628800
10  7 | 3 4   8  79 | 0-1,0-2,0-3,1-4,1-5,2-4,2-6,3-7,3-8,4-7,5-8,5-9,6-8,6-9,7-9 | 31.1,31.1,30.3                   3628800
10  8 | 3 3   6  84 | 0-1,0-2,0-3,1-2,1-4,2-5,3-6,3-7,4-6,4-8,5-7,5-8,6-9,7-9,8-9 | 31.4,31.2,31.6,31.13             3628800
10  9 | 3 3   2  82 | 0-1,0-2,0-3,1-2,1-4,2-5,3-6,3-7,4-6,4-8,5-7,5-9,6-9,7-8,8-9 | 31.4,31.9,31.12,31.5,31.3,31.7   3628800
10 10 | 3 3   6  84 | 0-1,0-2,0-3,1-2,1-4,2-5,3-6,3-7,4-6,4-8,5-7,5-9,6-8,7-9,8-9 | 34.2,33.19,34.6                  3628800
10 11 | 3 3   4  85 | 0-1,0-2,0-3,1-2,1-4,2-5,3-4,3-6,4-7,5-8,5-9,6-8,6-9,7-8,7-9 | 35.2,35.2,34.10,35.2,34.16,35.2  3628800
10 12 | 3 3   8  83 | 0-1,0-2,0-3,1-2,1-4,2-5,3-6,3-7,4-6,4-7,5-8,5-9,6-8,7-9,8-9 | 35.2,35.4,35.2                   3628800
10 13 | 3 3   2  85 | 0-1,0-2,0-3,1-2,1-4,2-5,3-4,3-6,4-7,5-6,5-8,6-9,7-8,7-9,8-9 | 35.4,36.1,36.1,35.3,35.2         3628800
10 14 | 3 3  12  81 | 0-1,0-2,0-3,1-2,1-4,2-5,3-6,3-7,4-6,4-8,5-6,5-9,7-8,7-9,8-9 | 37.1,37.1,37.1                   3628800
10 15 | 3 3   4  87 | 0-1,0-2,0-3,1-2,1-4,2-5,3-4,3-6,4-7,5-8,5-9,6-7,6-8,7-9,8-9 | 37.1,37.1,37.1                   3628800
10 16 | 4 3   4  91 | 0-1,0-2,0-3,1-2,1-3,2-4,3-5,4-6,4-7,5-6,5-8,6-9,7-8,7-9,8-9 | 41.1,40.34,40.10,40.8,41.2,41.2  3628800
10 17 | 3 3  16  90 | 0-1,0-2,0-3,1-2,1-3,2-4,3-5,4-6,4-7,5-8,5-9,6-8,6-9,7-8,7-9 | 43.2,43.4,43.2,43.6              3628800
10 18 | 3 3   8  90 | 0-1,0-2,0-3,1-2,1-3,2-4,3-5,4-6,4-7,5-8,5-9,6-7,6-8,7-9,8-9 | 44.4,44.14,44.10,44.4            3628800
10 19 | 4 3  16  93 | 0-1,0-2,0-3,1-2,1-3,2-4,3-5,4-5,4-6,5-7,6-8,6-9,7-8,7-9,8-9 | 48.2,47.4,46.82                  3628800
============================================================================================================================

The pair (n, id) is unique in the table. The columns are:

 n              number of vertices
 id             sequential number of a row
 d              diameter
 g              girth
 aut            the number of automorphisms
 wi             Wiener index
 edges          list of edges (vertices are numbered 0 through n-1)
 gn.antipodes   God's number and the number of antipodes

The column "gn.antipodes" provides God's number and the number of antipodes for each sliding puzzle on G. As an example, '25.1,25.1,25.1' means there are 3 nonequivalent choices of the goal configuration, but any of these choices yields a puzzle with God's number 25 and exactly one antipode.

The graph Gr is in the row (n = 10, id = 4).

A similar table for 12 vertices would have 85 lines.

Varikon Box 2x2x2 (edited 2 times)

I just figured out (n = 8, id = 1) is the Varikon Box 2x2x2. I get the same distribution as the one provided on the linked page. With symmetry reduction, I get the following:

=========================
  d     states cumulative  symmetric cumulative
-------------------------
  0          1          1          1          1
  1          1          2          1          2
  2          1          3          -          2
  3          2          5          -          2
  4          4          9          -          2
  5          8         17          -          2
  6         16         33          1          3
  7         31         64          2          5
  8         59        123          1          6
  9        113        236          1          7
 10        200        436          3         10
 11        330        766          5         15
 12        506       1272          6         21
 13        633       1905          8         29
 14        630       2535         16         45
 15        482       3017         18         63
 16        272       3289         14         77
 17        102       3391         13         90
 18         18       3409         10        100
 19          5       3414          4        104
=========================

Edit: In my original post, I forgot to link this page with which this thread overlaps (in particular, the 2x2 puzzle and polygons are mentioned).

Edit 2: As I wrote about 'solving small graphs mentioned in the literature', someone pointed out to me that the book "Sliding Piece Puzzles" by Edward Hordern includes several other puzzles which are in some sense designed as arbitrary-graph generalizations of the 15 puzzle (in particular, puzzles A5, A8, B60, E4 in that book). In an appendix to the book, David Singmaster mentions the generalization "to any network of points and lines with pieces placed on all but one point and a move consisting of sliding a piece along a line to the unoccupied point", providing references to the 1974 paper by R. Wilson and the book "Winning Ways" by Berlekamp, Conway and Guy. I also have missed the Lucky Seven puzzle from the latter book. According to my solver, the God's number of Lucky Seven is 62 (regardless of the goal configuration) which is twice the God's number of the 3x3 sliding-tile puzzle (with unoccupied corner in the goal configuration).

The underlying graph of the Lucky Seven puzzle
1 * * 0 * * 7
*     *     *
2     *     6
*     *     *
3 * * 4 * * 5