A few days ago when Thomas was toying with the Rubik's Cube a interesting question came up. Will a set series of moves repeated eventually bring the Cube back to the origin arrangement? I thought about the question for a bit, and responded that it would. I'm curious if anyone also had any thoughts on the subject-- and if you're not interested, I'm not surprised in the least.

My thoughts about the problem were as follows, and for simplicity's sake I will refer to the origin arrangement as "solved."

Hypothesis(1): That any set of moves of an arbitrary size will, upon repetition, bring the cube back to solved.

Proof:

Assume(1): That there is a set of moves that will, upon repetition, never solve the cube.
Assume(2): This set of moves will never find a non-solved arrangement a second time.
Fact: There is a finite number of states for the cube.
Fact: If that move set was done more times than that number, it would find a non-solved arrangement a second time.
Conc(1): Assume(2) is false.

Assume(3): This set of moves can visit a non-solved arrangement any amount of times without visiting the solved state a second time.
Fact: If we treat this non-solved arrangement as the origin and do the move the proper amount of times, it will visit this arrangement again.
Conc(2): Assume(1) is false.

Fact: If Assume(1) is false, Hypothesis(1) is true.
Conc(3): Hypothesis(1) is true.


Conclusion:
Any given set of moves, upon repetition, will bring the state of the cube back to the origin state. It just might take a very, very long time.

More interesting questions, some of which beyond my level.
1. What is the set of moves which takes the shortest to terminate?
2. The longest?
3. What is the set of moves which visits the smallest amount of permutations before termination?
4. The largest amount?

The first and third I can answer. The set of moves for both cases is any one face-turn repeated four times, it only requires one application (1) and only visits one state (3).

Any thoughts on questions 2 and 4? Criticisms of my logic? Random comments?

Rubik's Queue

Recently I have gotten into Rubik's Cubes, and have judged them to be one of the most fantastic toys ever created. I am currently trying to solve the thing by ingenuity alone, without looking online for solutions.

Satan Incarnated into a 3v3v3 Cube

I've gotten the first two layers down cold, and can form a correct cross shape on the bottom and think I can solve the yellow face (but have things in the incorrect place, including the cross). I hope to be able to do both soon.

While neglecting studying for finals and struggling with ideas, I decided to kill two thousand avians with one monolith and write a program to both study for the final and solve the cube.

My Savior

I started out by building a representation system. It was a fairly simple idea: arrays of arrays. Imagine a giant filing drawer, with indexes. In each spot is some object. It could be a word (String), a number (int) or anything. A simple array would look like this:

[9][7][32][42]

My system was to create an array of arrays, three by three, and create six of them (one for each face). They would store numbers, which corresponded to colors:

[ [1][1][1] ][ [1][1][1] ][ [1][1][1] ]

or rather,

[1][1][1]

[1][1][1]

[1][1][1]

This would be the solved white face. This method makes checking to see if the cube was solved very easy.

The moves would do certain things to the arrays, switching numbers among the faces. I decided to create two methods, turn and turn prime. They would input certain faces, and move them accordingly. Creating the regular twelve moves (F, F', L, L', B, B', R, R', U, U', D, D') were easily done, for I would just input certain faces into the turn and turn prime methods.

So far so good. Having the user input the cube wasn't too much of a hassle either, and using some simple methods I was able to create some simple code to input each side following the aforementioned number concept.

Now I could input faces and move them in any direction I wanted, as well as check for a fully solved cube. And all of this was programmed in around the space of one or two hours without any real thought.

I still had to do the actual intelligent stuff, namely, solving the cube (which I can't do normally). I decided to take a simple, time-consuming, and methodical approach using queues.

A queue is your typical grade-school lunch line. First person in the line is the first person getting food, or more generally, First In, First Out (FIFO).

Real-World Queue

The idea was simple: take the inputed cube, and put it onto the queue. While the cube on the end of the queue is not solved, take the first cube off of the cube, and move it in each possible direction, each time putting that new cube onto the queue. Essentially, this would, in a breadth-first fashion, try every possible sequence of moves starting from the original cube, and create a new cube for every single permutation in a breadth-increasing order.

Now, here are some fun facts:

The number of possible combinations for cubes without disassembly is:

8! x 3^7 x 12! x 2^10 ~= 4.33 x 10^19 or forty-three quintillion.

It has been suggested (and claimed proved) that all unsolved cubes can be solved in less than 23 moves.

This is how many variations my program would visit:

The first time I had one cube, or 12^0. The second round I would create twelve new cubes, one for each move, or 12^1. A pattern arose:

12^0 + 12^1 + 12^2 + 12^3....+12^22 ~= 6.022 x 10^23

My Computer

I was shocked when this turned out to be a mole of cubes. I think that the reason that this number is substantially bigger than the number of combinations is that my algorithm would visit many duplicate cubes.

Needless to say, I wasn't terribly surprised when my compiler spat out a “Memory Overflow Error.”

So I am currently trying to write a complex program which will actually use the methods that I'm discovering and might use the exhaustive search once I get it down to a simple problem. I've lost much enthusiasm for the project though, given that I probably should actually study.