Home »

Revisiting Korf's 3x3x3 Counts And Identifying Duplicate Positions

Submitted by NoLongerUnsolve... on Fri, 06/10/2016 - 21:18.
A while ago I generated a corners database for the 3x3x3 subset of positions that are applicable to the 5x5x5 cube. I used a move generator that generated 27 moves at depth 1 instead of the commonly reported 18. My move generator also spawned the middle slice turns along with the familiar turns of the outer faces. The total positions reported for the corners database agreed in the end.

Recently I decided to implement the Korf move generator. In my mind, it is really more akin to a 2x2x2 move generator, since every move sequence that is generated can also be played out on a 2x2x2 cube. (Contrast that to some 5x5x5 moves which clearly have no counterpart of smaller cubes.) My move generator started with the solved cube, counted nodes as a function of depth, and placed each unique cube in a hash table, flagging all of the duplicate positions that came next.

From depths 1 through 3, there were no duplicate positions. At depth 4, there were 15:

======================================================================================

Line of play: L2 U2 D2 R2 is a duplicate of R2 U2 D2 L2
Line of play: L2 U2 D2 L2 is a duplicate of R2 U2 D2 R2
Line of play: L2 F2 B2 R2 is a duplicate of R2 F2 B2 L2
Line of play: L2 F2 B2 L2 is a duplicate of R2 F2 B2 R2
Line of play: U2 D2 R2 L2 is a duplicate of R2 L2 U2 D2
Line of play: D2 R2 L2 U2 is a duplicate of U2 R2 L2 D2
Line of play: D2 R2 L2 D2 is a duplicate of U2 R2 L2 U2
Line of play: D2 F2 B2 U2 is a duplicate of U2 F2 B2 D2
Line of play: D2 F2 B2 D2 is a duplicate of U2 F2 B2 U2
Line of play: F2 B2 R2 L2 is a duplicate of R2 L2 F2 B2
Line of play: F2 B2 U2 D2 is a duplicate of U2 D2 F2 B2
Line of play: B2 R2 L2 F2 is a duplicate of F2 R2 L2 B2
Line of play: B2 R2 L2 B2 is a duplicate of F2 R2 L2 F2
Line of play: B2 U2 D2 F2 is a duplicate of F2 U2 D2 B2
Line of play: B2 U2 D2 B2 is a duplicate of F2 U2 D2 F2

At depth 5, there are 372.
At depth 6, there are 4292.
At depth 7, there are 20184.
At depth 8, there are 118873.

I stopped there for now.

My supposition at this point is that the duplication is somehow a function of the symmetry of the solved cube at the start, since I see no reason why these moves need to be disqualified from the overall node count. I seem to recall Bruce mentioning something like this to me a while back.

My big question is: Why is it generally accepted that there are only 18 unique nodes at depth 1? Clearly I can make 27 unique moves on a 3x3x3 cube from the solved state.

---Ed Trice
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

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

After the Rubik's was invente

Submitted by Bruce Norskog on Sat, 06/11/2016 - 20:12.

After the Rubik's was invented, mathematicians tended to consider moves of just the outer layers, tending to view inner layer turns as movements of two opposite layers. This view keeps the center pieces fixed and form a reference with which the rest of the pieces must be placed. The 43,252,003,274,489,856,000 legal configurations of the other pieces formed a mathematical group which came to be called "the cube group."

They used the term quarter turn metric for the case where only quarter turns of the outer layers were allowed, and half turn metric for the case where half turns of the outer layers were also allowed. Over time more interest developed for the use of inner layer turns, especially after larger cubes became available, and turning only outer layers was obviously not sufficient for solving the larger cubes. Many people now prefer to say face turn metric instead of half turn metric.

In considering there to be 27 positions one move from solved, you are using what is called the 3x3x3 slice turn metric. There is this thread where slice turn metric data is discussed. Since you appear to generally want to use metrics that allow any single layer at a time to be moved, using the 3x3x3 slice turn metric as a pruning table for the corners makes sense.

» login or register to post comments

Thanks Bruce. And, not onl

Submitted by NoLongerUnsolve... on Thu, 06/16/2016 - 18:12.
Thanks Bruce.

And, not only do I "appear" to prefer the slice turn metric, it's an actual fact! But I appreciate you not jumping to any conclusions.

:)
» login or register to post comments

Problem with the slice turn metric

Submitted by Jerry Bryan on Sat, 07/16/2016 - 11:55.
It seems to me that the slice turn metric for the 3x3x3 cube has a problem common with the 2x2x2 cube and with any void cube of larger size larger than the 2x2x2 in that the absence of a frame of reference makes counting moves extremely ambiguous. For example, take the Start position in the slice turn metric and perform the move sequence RL'M where M is the middle layer between R and L and the move M rolls the middle layer "forward" along with the move R. The cube now appears to be solved and it appears to be 0 moves from Start rather than 3 moves from Start.

Curiously, the behavior of most computer models of the cube deviates in this regard from an actual cube you hold in your hand. My favorite example is the 2x2x2 cube where the Start position appears to be restored after the sequence RL'. In some computer models for the 2x2x2 cube, the state of the cube would be different after the move sequence RL' than before the move sequence RL'. Which is to say, some computer models for the 2x2x2 cube are equivalent to a computer model for the corners of the 3x3x3 cube in that whole cube rotations are different states of the model. However, for a physical 2x2x2x cube that you hold in your hand you would normally consider the 2x2x2 Start position to be solved after RL' or after any whole cube rotation. Indeed, the most common solution to this ambiguity in computer models of the 2x2x2 cube is for the model to disallow moves of opposite faces. For example, the model allows moves of the R face but not the L face or vice versa.

Another example is the occasional debate about whether it is even necessary to model the face center cubies of the 3x3x3 cube. As long as you stick with face turn moves, the size of the group and the structure of the Cayley graph are identical whether you model the face center cubies or not, so you don't need to model them. This can be very confusing because it would seem very natural to model a void 3x3x3 cube (for example) simply by omitting the face centers. But if omitting the face centers doesn't change anything then how do you model a void cube? My solution for modelling the void cube is to treat positions that differ only by whole cube rotations as equivalent.

This gets us back to the slice turn metric for the 3x3x3 cube. What are you going to do about positions that differ only by being whole cube rotations of each other? Maybe a solution would be to model slice turns such as the M slice which I described above as being equivalent to LR'. In this case, we are back to where we don't need to model the face centers. The sequence RL'M would become the sequence RL'(LR'). The (LR') sequence is just a description of the slice move and it only counts as 1 move. So after the 3 move sequence RL'(LR') you really would be back to the Start position.

Jerry
» login or register to post comments