SudoKill

Whilst perusing the internets I came across the following site. Normally I'm not a big fan of sudoku, but this game looked interesting enough. The goal seems to be to trap the other player into a situation where he has no legal moves (there are constraints to where you can place a number). The strategy looks interesting enough. I might even challenge some of you to a game like this when I see you next.

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.