Depth   New            Total
0       1              1
1       6              7
2       18             25
3       54             79
4       162            241
5       486            727
6       1457           2184
7       4360           6544

Introduction

On 02/23/2016, I posted a message about a new program I had developed that had succeeded in enumerating the complete search space for the edges only group. It was not a new result because Tom Rokicki had solved the same problem back in 2004, but it was important to me because the problem served as a testbed for some new ideas I was developing to attack the problem of the full cube. I am now in the process of adapting the new program to include both edges and corners. In this message, I will include some additional detail about my new program that was not included in the first message.

In 2002, Korf and Felner [1] used pattern databases to solve optimally 50 random instances of the 5x5 sliding puzzle. They used a static 6+6+6+6 partition of tiles (described below), along with its reflection in the main diagonal. In a 2004 paper by Felner, Korf and Hanan [2], the authors describe in a footnote the way they handled the empty tile as 'not trivial'; the empty tile was taken into account when precomputing the database, but then the tables were compressed by discarding the information about the empty location. The authors do not provide the distribution of values from the pattern databases, but do provide maximum values and the number of nodes generated when solving random instances of the 5x5 sliding puzzle.

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 v₀ and 'sliding' the piece at v along the edge (v; v₀). 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.

Continuing my work with the 3x3x3 super group, I have written a coset solver for cosets of the pure center cubie subgroup. This subgroup is made up of the 2048 even parity center cubie configurations composed with the identity edge and corner configurations. The super group may be partitioned into cosets of the pure centers subgroup, g * [CTR] , where g is an element of the super group and [CTR] is the centers subgroup. The centers subgroup is a normal subgroup of the super group, g * [CTR] = [CTR] * g, and the standard cube group is the quotient group of the super group and the centers subgroup.

Super Cube States at Depth

I've been working with the super cube group (the 3x3x3 cube with center cubie orientation). There are two earlier threads here dealing with this group, Lower bounds for the 3x3x3 Super Group and Supergroup knowledge. Neither of these contain any states at depth information. To test my model I have performed a breadth first states at depth enumeration of the group out to depth 10 in the qtm. Can anybody confirm these numbers for me?