Today I finished up some of the coding for the my Rubix Cube project using Direct X and LINQ. Luke Hoersten and Nate Hobbs were my partners in developing the program. All of us worked on coming up with designing a sufficient data structure. I worked on implementing the data structure and the user interface / Direct X stuff. Luke focused on refactoring the code, and coming up with parts of the solving algorithm. Nate worked on parts of the solving algorithm.
Previous Posts
I have outlined some problems we had while developing the application and also some design decisions that were made to include LINQ. The way our program solves it is that it goes about it the way that a human would.
Solving the cube
The program starts with trying to solve the bottom layer, then solve the middle layer, then finally the top layer. Luke would be able to give a much better explanation of how it worked. It was suggested by our professor that we create a tree by attempting every move, then for every move try every move, etc… This we thought would not be a great way to solve it for two reasons. The first being that there are 18 possible moves to make on a cube, and if you want to try and go n levels deep, it would have to compute 18n states. Not only that, but it would have to store every state, score them, then take the path with the best score. To go 6 levels deep, you need to compute 34 million different states, for 7 levels deep, you need to compute 612 million states. Computers are good, but they aren’t that good.
This would not be completely terrible, if you had a smart heuristic for scoring. If every time you computed every one of those states, you were guaranteed to get closer to the solution, then you would only be spending time solving it, and time a computer has. The heuristic that was presented was to find proximity of where a block is to where it should be. This is not the greatest either because what happens when you are almost finished solving it, and you have only one or two cubes out of place (or oriented wrong). You have to end up messing up your cube really bad in order to solve it, and if you’re algorithm doesn’t go deep enough, you won’t find your solution because your current state will always be better than where you are going.
The Program
Basically, here is the outline of the program:
Block.cs – A tiny block within the rubix cube. The rubix cube contains 27 of these blocks.
Cube.cs – The cube structure, contains helper functions to orient and move sides of the cube.
Solver.cs – The class that solves the rubix cube.
UI.cs – Handles the DirectX and drawing of the rubix cube.
We haven’t formally licensed the program, but I’m sure Luke and Nate wouldn’t mind if we say it’s GPL’d. Basically give us credit for whatever you do with it and don’t sell it.
URL: Rubix Cube in C# using LINQ
Alternatively, you can also check out the Mercurial sources at: Luke’s Mercurial Sources