Discussions on the mathematics of the cube

Enumerating all of 3x3x3 cube space - required performance characteristics

I've been playing around with what it would take to enumerate the entire cube space for the standard 3x3x3 cube, using a large number of computers working together.  I've come up with what I think is a reasonable approach, a bit past the bare edge of what might be possible with today's technology, but perhaps not too far past.  The assumption will be that we want to solve the problem in one year, with all the machines involved in the project fully dedicated to the problem for the whole year.

The following is not a compete description of my proposed approach, but rather is an analysis of the performance characteristics that would be required.  There is not much advantage in coming up with an approach that would require billions of years to compute.

First Post, General Puzzle Solving

Hello.

A quick introduction: I'm Robert Smith, I'm 18, and I live in the US. I used to be quite into speedcubing, starting around 2003, but I have since moved into the more "theoretical" aspects of the cube. I also like mathematics, and, fortunately, programming. Anyway, that's that.

I have been writing a "general puzzle solver," whose goal is to be able to solve any (permutation) puzzle with (almost) any method. Quite quickly, we see there are definitely limits to this (e.g., we couldn't solve any scrambled 10x10x10 cube in a single phase). But, if some certain requirements are met, solving any puzzle should be an ability with this program.

Superflip

I've read that the proof of the superflip requiring a minimal solution of 20 moves relied heavily on the symmetry of the position and is purported to be quite clever. I just found it in the cube lovers archive, but haven't had a chance to read it in depth, yet.

Has anyone posited other positions that could be proved to require 20 moves similarly? Has it be postulated that the superflip could be the only position that requires 20 moves?

Thanks,
e.

U turn sans U turns

All elements of the Rubik's cube group may be generated using turns of only five of the six faces, say all but the Up face. This suggests a puzzle variant: a cube with the Up center cubie glued fast. Has any work been done on such a puzzle? I played with this a bit today. Here's an U turn macro using no U turns:

B D' F L' F' B D F' R B' L F' D F B' L' F

Upgraded to apache 2.2.9 and php 4.4.9

Did another long overdue upgrade with apache and php. There's tons of new exploits so it has to be done. We were down for about an hour. Looks like everything still works :)

Mark

Twenty-Two Moves Suffice

With a total of 1.28 million cosets solved, we have shown that every position of Rubik's cube can be solved in 22 or fewer face turns.

This required approximately 50 core-years of CPU time contributed by John Welborn and Sony Pictures Imageworks.

No distance 21 positions were found in this search, despite solving a total of more than twenty-five million billion cube positions.

There is a short article in New Scientist (August 9th edition) on this problem and this result.

The same techniques for the proof of twenty-five moves were used, just on many more computers.

I have found 310 cosets with an upper bound of 18, and about 82,000 with an upper bound of 19 (or less); all the rest have an upper bound of 20 or less.

Supergroup knowledge

What is known about the supergroup? (That is, the normal cube but with oriented
center facelets.) Have any computer explorations been performed? Any "hard"
positions known? Any coset explorations?

I know Jaap has a supergroup solver embedded in a Java applet. Does anyone else have
any programs?

A start might be an optimal solution length distribution that take a solved cube to a
solved cube, but just change the center facelet twists. But maybe an optimal solver
for the supergroup would just be too slow.

My diploma thesis - Human method evaluator

Recently I finished my diploma thesis. It's about Hume, a program I wrote for evaluating human solving methods for twisty puzzles. The main goal is to let the user describe a method in a minimal way so that new method ideas can be tested quickly and with ease. The program fills in all the dirty work. So far it's less powerful than I'd like it to be, but I'm happy with what I got from it so far, and I'm happy with my thesis (my professor liked it very much, too, which made me even happier). The thesis is online now, the program will follow soon:
http://stefan-pochmann.info/hume/

Cheers!
Stefan

Complete Search of Subgroup Defined by Edge Cubies

I recently completed a complete breadth-first search of the subgroup of the 3x3x3 cube defined only by the edge cubies. In other words, think of a cube where all the corner cubies are indistinguishable, and a state is defined only by the edge cubies. It took about 35 days on a dual-processor workstation, with three terabytes of disk storage. This was done without any use of symmetries. Here's the number of unique states at each depth:

0 1
1 18
2 243
3 3240
4 42807
5 555866
6 7070103
7 87801812
8 1050559626

Twenty-Three Moves Suffice

After solving more than 200,000 cosets, we have been able to show that every position of Rubik's cube can be solved in 23 or fewer face turns.

The key contribution for this new result was 7.8 core-years of CPU time contributed by John Welborn and Sony Pictures Imageworks, using idle time on the render farm that was used for pictures such as Spider-Man 3 and Surf's Up.

No distance 21 positions were found in this search, despite solving a total of more than four million billion cube positions.

The same techniques for the proof of twenty-five moves were used, just on many more computers.