Hi folks,

My upstream has changed my ip address so now the numeric ip is 69.165.220.244. All the links should work as before once all the dns changes have propagated.

To improve security I've removed ftp access from the forum. We'll use http instead of ftp. I've also moved the Thistlethwaite files over so they can be accessed by http as well.

Even though it's only confirmation of some rather ancient results, I would like to report that I have succeeded in replicating Tom Rokicki's 2004 results concerning the edges only cube in the face turn metric reduced by symmetry.  My goal was not really to solve that particular problem.  Rather, it was to use that problem as a way to prototype some ideas I have had for improving my previous programs that enumerate cube space.

The base speed of my program is that I am now able to enumerate about 1,000,000 positions per second per processor core when not reducing the problem by symmetry, and I am now able to enumerate about 150,000 symmetry representatives per second per processor core when reducing the problem by symmetry.

Bruce Norskog designed a five stage procedure to solve 4x4x4 positions, where the last stage is solving inside the squares subgroup. When I rewrote the code in Java to be used for the official WCA scrambler program, I found a few improvements on coordinate representation and symmetry reduction that I think is worth sharing.

Except for the last stage where centers need to be solved, every other stage needs to place 8 centers from a single axis (RL, FB or UD centers) in their correct faces (RL, FB or UD faces), in one of the 12 positions that can then be solved using only half turns. However, as pointed by Shuang Chen in his analysis, we don't need to store the exact colours of centers but only if two centers have the same or different colours. This reduces the number of center coordinates by 2.

Also, as opposed to the 3x3x3, 4x4x4 does not have fixed centers, which allows us to do more symmetry reduction. I'm representing a sym-coordinate as:
s1 * g * < H > * s1' * s2'
where g * < H > is a coset, s1 and s2 are symmetries from subgroups S1 and S2 of the group M of symmetries of the cube. s1 is the usual conjugated symmetry, and s2 correspond to a rotation of the cube, which is possible on the 4x4x4. Using carefully chosen subgroups S1 and S2 for each stage, more symmetry reduction is achieved. I will be using the Schoenflies symbols for subgroups of M in the following.

There was a router problem last night, possibly due to memory corruption. I disconnected and reset everything on the router and DSL modem and now it's working again.

Sorry about the outage. Just letting everyone know that the forum is still alive :)

Mark

I have replicated Shaung Chen's upper bound result of 57 moves in the OBTM (outer block turn metric), reproducing his numbers and calculating depth counts without symmetry reduction. His results are here: http://cubezzz.dyndns.org/drupal/?q=node/view/525

I have also calculated, with the same code, results in two other metrics: SST (single slice turn) and BT (block turn). The final results lower the upper bounds in these metrics to 56 and 53 (respectively).

The sequence of subsets chosen is identical to that used by Chen. The maximum distance for each stage, the sum, and the current lower bound is shown here:

I developed a slide-puzzle called WrapSlide that reminds of Rubik's Cube. I am interested in determining God's number for WrapSlide. I think my initial approach is too naive and may be I should leave it to the experts.

First let me describe WrapSlide:

The main puzzle is a 6x6 grid of colored tiles which are separated into four quadrants of 3x3 tiles. When it is unmixed all the tiles in a quadrant have the same colour. A move consists of sliding either the top, bottom, left or right two quadrants of tiles 1 to 5 units horizontally or vertically. Stated differently, a move consists of sliding either the top, bottom, left of right half (consisting of 3 rows or 3 columns) relative to the other half, thus giving 4x5 possible moves to choose from. As with Rubik's cube the puzzle is to return it to its unmixed state after it is scrambled. (For the unmixed state we don't care which color goes into which quadrant)

Breadth First Enumeration
2014-09-27 19:58:23.094 VoidCubeClient[508:5903]  0             1             1
2014-09-27 19:58:23.095 VoidCubeClient[508:5903]  1             1            12
2014-09-27 19:58:23.099 VoidCubeClient[508:5903]  2             5           114
2014-09-27 19:58:23.101 VoidCubeClient[508:5903]  3            17         1,068
2014-09-27 19:58:23.105 VoidCubeClient[508:5903]  4           130         9,951
2014-09-27 19:58:23.133 VoidCubeClient[508:5903]  5         1,018        92,592
2014-09-27 19:58:23.333 VoidCubeClient[508:5903]  6         9,204       860,852
2014-09-27 19:58:25.033 VoidCubeClient[508:5903]  7        83,789     7,991,856
2014-09-27 19:58:40.300 VoidCubeClient[508:5903]  8       774,323    74,114,319
2014-09-27 20:01:03.984 VoidCubeClient[508:5903]  9     7,159,250   686,774,712
2014-09-27 20:25:47.908 VoidCubeClient[508:5903] 10    66,273,224 6,360,091,030


Coset Enumeration

Void Cube Model 1.0
	Group: R, U, F, TR, TU, TF
	Coset Base Subgroup: Subgroup with solved corner cubies and the
	   UF and UR cubies in the solved position regardless of orientation.
	484,989,120 cosets of size 7,431,782,400
	Coset Symmetry Reduction: Oh+

Cosets solved since launch: 3,429,943
Average time per coset: 0:00:00.068

Server Status:
Void Cube Enumerator Server

Enumeration to depth: 13

Snapshot: Friday, October 3, 2014 at 6:56:34 PM Central Daylight Time

 Depth             Reduced             Elements
   0                     1                    1 
   1                     2                   12 
   2                    18                  114 
   3                    50                1,068 
   4                   447                9,951 
   5                 2,008               92,592 
   6                19,000              860,852 
   7               124,184            7,991,856 
   8             1,136,806           74,114,319 
   9             9,028,936          686,774,712 
  10            82,411,850        6,360,091,030 
  11           711,657,402       58,868,124,048 
  12         6,507,640,604      544,562,369,684 
  13        58,275,341,089    5,033,855,951,932 
  
 Sum        65,587,362,397    5,644,416,382,171 

484,989,120 of 484,989,120 cosets solved

Elapsed Time: 0:12:14:50

This work was performed using the <R, U, F, TR, TU, TF> group model. This model was discussed in a previous thread. It must be pointed out here that the <R, U, F, TR, TU, TF> metric is exactly the same as the <R, U, F, L, D, B> metric since TR = L , TU = D and TF = B on the void cube. It makes no difference if the left face is rotated holding the rest of the cube rigid or if the left face is held rigid and the rest of the cube is rotated in the opposite direction, the rearrangement of the cubies is the same. If a distinct state of the void cube is at say depth 13 in the <R, U, F, TR, TU, TF> metric it will be at depth 13 in the <R, U, F, L, D, B> metric.

The goal is to provide a general statement about the orientations of pieces of a certain permutation puzzles. Since there are so many different kinds of permutation puzzles we will have to exactly describe the properties of the puzzles for which the statement will be valid. We also will have to explain how the orientation of pieces can be measured for these puzzles in way as general as possible.

Then we are able to show that under these assumptions for a given kind of pieces with k possible orientations the sum of the orientations of all these pieces module k is invariant under permutations.

We restrict our consideration to permutation puzzles which do not change their shape. We call the moving parts of the puzzle the pieces and the locations of the pieces the places of the pieces. For three-dimensional puzzles we assume that the pieces are polyhedrons which are bounded by faces, for two- dimensional puzzles we assume that the pieces are polygons which are bounded by a circuit of edges. Since our main goal is the examination of three-dimensional puzzles we only use the term "faces" in the following text, but it could be replaced by "edges" to handle the two-dimensional case.

We further assume that at least some pieces can occupy their places in different positions/orientations. Since we restrict to puzzles which do not change their shape, these pieces must have at least one axis of rotational symmetry. We restrict our consideration to puzzles where the different orientations of a piece are defined by exactly one axis of rotational symmetry of order k (which does not seem to be a significant restriction). In this case we pick an arbitrary face which is not fixed by the symmetry and name it f_0. A counter clockwise (as seen from outside the puzzle) rotation by 2Pi/k*j, 1<=j<k, then maps f_0 to another face, which is denoted by f_j. The faces f_0, f_1, f_2... may be visible or not. The faces f_0, f_1 and f_2 of a Rubik's cube corner are for example visible while for the centre pieces of a 4x4x4 cube the faces f_0, f_1, f_2 and f_3 are not visible.

To define the orientation of a given piece at any possible place in any possible position we define a reference frame for the orientations. The geometric positions of the faces f_0, f_1... of a piece at a certain place of the puzzle we call slots. It is important to emphasize that only the faces move when a permutation is applied, not the slots. Applying a permutation, the slots of the places just are "filled" with the faces f_0, f_1... of a different piece of the same kind. Now we arbitrarily choose exactly one slot of every place to and call it the reference slot. We say that the orientation of a piece in this place is i if the reference slot is filled with the face f_i of that piece.

A move M of the puzzle is a permutation of some of its pieces. We hardly can establish any statement about the orientations of the pieces if there is no restriction on the permutations. We call a place P M-unambiguous if applying move M one or several times we cannot have the same piece in different orientations in place P. A place which does not have this property we call M-ambiguous. For example, for all nxnxn Rubik's cubes all places are X- unambiguous for all conceivable moves X except for odd n in the places where the face diagonals meet.

A move M usually affects several pieces and places. If we choose a piece p at a place P_0 this piece p usually visits several places P_0,P_1,... if we apply the move M several times. All the pieces which occupy these places form the M-orbit of p. All these pieces have the same shape as p and the involved places P_0, P_1... are all M-unambiguous or all M-ambiguous. The orbits of any piece of nxnxn Rubik's cube except the centre piece for odd n consist of 4 pieces for example.

With these preliminary considerations we are now able to establish the following proposition:

Proposition 1: Let M be a move of a permutation puzzle which does not change its shape and p a piece with a single k-fold rotational symmetry in a M-unambiguous place P. Then the sum of the orientations of all pieces in the orbit of p does not change its value modulo k if M is applied.

Proof: We name the involved places and slots in a way that it is easy to keep track of the orientations when the move M is applied. The place of piece p is named by P_0, the slot which is filled by face f_i (0<=i<k) of p is referred to as slot_i. Let the size of the M-orbit of p be s. Then applying M j times (0<j<s) moves piece p to a place which we call P_j. The slots of P_j are denoted in the same way as for P_0, using the faces of p – now in place P_j - again as a reference to name the slots. Named in this way we can make the following observation in the table which describes the faces of all pieces of the orbit in the slots of their place:

The faces in the slots of P_0 are well defined by the definition of the slot names. For other places, place P_2 for example we neither know the piece in P_2 nor the face in slot_1 but since the faces of all pieces in the orbit are named in the same way counter clockwise we know that we have face_(a+1) mod k in slot_2 of P_2 and face_(a+2) mod k in slot_3 of P_2.

And most important, in the way the slots and places are named, if we apply move M all entries of the table are cyclically shifted one line down, the entries of line P_(s-1) move to line P_0 (this would not work if the places would be M-ambiguous).

With the following example we show that the sum of the orientations modulo k does not change when applying move M. The orientations are defined by the reference slots which can in principle be chosen arbitrarily, they are highlighted in the example below. Obviously there has to be one reference slot in a line, but for the number of reference slots in a column there are no restrictions.

Before applying move M:

According to the definition of the orientations the sum of the orientations in the orbit modulo k is

Finally we have shown that 26 or fewer moves suffice to solve any position
of the Rubik's Cube in the Quarter-Turn Metric.

We put up a page with basic information at cube20.org/qtm.

I'm starting this forum topic for discussion; sorry I did not post this when
we made the announcement!