|
About
A while ago I bought a Lego Mindstorms kit for my two daughters. But sad to say, they have not had much access to it yet ;-).
After building a tribot and a line follower I wanted to create something more spectacular.
Having seen Rubik's cube solvers by JP Brown, Markus Mack and Daniele Benedettelli I decided to try to create my own Rubik's cube solver.
The goal was to build a standalone Rubik's cube solver from the standard NXT kit.
This was a very interesting project with many different problems to solve.
The mechanical solution.
The mechanism looks simple but there's a lot of work behind it. And many rejected solutions ;-).
Reading the colors using only a light sensor.
Detecting the colors of the cube was one of the trickiest parts of the project. I use the raw light sensor value. But many of the colors gives almost the same values and are impossible to separate from each other. I had to replace some of the colors to solve that problem.
After the faces of the cube are read the colors are resolved using a best match algorithm. The center color readings are used as reference. It then finds the corner pieces that best matches the reference values. The reference values are recalibrated using the these corner pieces. Last it finds the edge pieces that best matches the reference values.
With this approach it is possible to resolve the colors even if the color ranges are a bit overlapping
The next challenge was to implement an algorithm to calculate the moves to solve the cube.
I first implemented an algorithm based on a general layer by layer solution. I wrote the program in C, tested it out and ran a lot of simulations before porting it to NXC.
I was concerned about whether the size of the program or the speed of execution should be a problem. The size wasn't really a problem. The speed I had to work on. Compared to a PC the NXT is much slower. The same time it takes for the NXT to calculate a solution, the PC calculates solutions of thousands and thousands of randomized cubes.
The first algorithm had an average of 97 moves to solve a cube. I thought I could do better. I implemented a corners first method based on a method by Victor Ortega and Josef Jelinek which I combined with a method from Gaétan Guimond. This gave an average of 60 moves (and was faster to calculate).
It was a real thrill the first time Tilted Twister succeeded solving a scrambled cube.
Since I put up the Tilted Twister web site I have received lots of mail asking for building instructions and program.
I have now created LDD-drawings and published it on this site. I have also published program and source code free to download.
If you have any comments or suggestions, feel free to contact me.
Hans Andersson
| 
About