After the video of my most recent ARM Powered Android LEGO Speedcuber robot became so popular, I thought that it would be a while before I was involved in creating another. I should have learned from previous experience that this might not be the case... however, this time I only have myself to blame for the idea! See the new 7x7x7 "MultiCuber" solver video and read about how I achieved it.
About 18 months ago I was inspired to design and build my first LEGO robot (video) controlled by a Nokia N95 mobile phone that could solve a regular 3x3x3 Rubik's Cube. While demonstrating this robot to a few colleagues at ARM, I had some other puzzles lying on the desk including 4x4x4 and 5x5x5 Rubik's Cubes. A number of people asked if the robot could solve any of these larger puzzles. I said "no" and added that they would be physically much harder to solve than the 3x3x3 since the robot would have to be able to turn both the outer faces and also the second layer of pieces. I dismissed the thought until my colleague, John, pursued the idea and suggested a way of adapting the original mechanism to allow the second layer to be manipulated. The result was the ARM Powered LEGO/Nokia 4x4x4 Rubik's Cube Solver (video) that you may have already seen.
The software that I originally wrote for the 3x3x3 solver was a simple, procedural implementation based on the method I worked out to solve the puzzle by hand when the Rubik's Cube first became popular. However, I quickly re-implemented this as a lookup table-driven algorithm in order to allow more efficient solutions with fewer moves to be determined. In both the procedural and table-driven versions, the solution is found in a number of stages. Each of these stages solves a group of a small number of pieces while preserving the position of all of the pieces previously solved. At each stage, the table contains an entry for each possible position of the next group of pieces to be solved with a pre-determined sequence of moves to solve the group. The table-driven approach allows the size and combination of pieces in the groups solved at each stage to be chosen to make trade-offs between the number of stages, the number of table entries and the average and maximum length of move sequences at each stage.
Typically, humans solve the puzzle in a similar way using groups of one or two pieces for most of the cube up to three or four pieces towards the end of the solve. The tables for my faster Speedcuber solvers (see my first blog here) allow groups of up to six pieces to be solved in five stages with far fewer total moves than an average human solver. Extending the table-driven 3x3x3 solver to solve the 4x4x4 puzzle was relatively straightforward by supporting moves that turn either one or two layers. In order to keep the overall lookup table size reasonably small, the groups' sizes were kept small resulting in the number of stages being increased to about twenty.
As I mentioned above, I thought that the 4x4x4 solver and the high-speed 3x3x3 Speedcuber robots would be the end of my series of robots. However, ever since the original challenge to solve cubes larger than 3x3x3, even after the success of the 4x4x4 solver, I couldn't help thinking about the larger cubes (actually, maybe I can blame someone for this latest distraction from my main job after all - John!?!).
I was reasonably confident that extending the 4x4x4 algorithm to cope with larger cubes would be relatively easy. I decided to write an application that would be able to solve a cube of any size. Initially this involved identifying the different classes of piece that exist on cubes of different sizes. For example, 2x2x2 cubes (yes, they exist too!) only have "corner pieces". 3x3x3 cubes have corners and also "edge pieces" and "center pieces" (although the single-color centers can only rotate). The 4x4x4 introduces "middle pieces" (the four single-color pieces in the middle of each face that can move between faces). I continued thinking about larger cubes until I determined that, according to my classification, no new types of piece occur on cubes larger than 7x7x7. Having classified all the pieces, I was able to write a generic algorithm and generated a set of sixty-four lookup tables that could solve a scrambled cube of any dimension limited only by RAM and processor time. I tested this algorithm on virtual cubes as large as 100x100x100.
Things were going well...
The "obvious" challenge after the 4x4x4 cube would have been the 5x5x5 puzzle. Theoretically, the existing 4x4x4 solver could have been adapted mechanically to solve this puzzle since, despite having five layers, it is only necessary to be able to turn the outer two layers on each face to be able to solve it, rather like the 4x4x4. However I was very uncomfortable with this approach. Firstly: the previous 4x4x4 robot was slow - it took over nineteen minutes to solve. Secondly: it was mechanically a little unreliable since it lifted and rotated the cube by gripping it between two small rubber tyres (LEGO of course) and the smooth surface of the cube meant that occasionally the cube would drop at a slight angle and jam the robot. I have to confess it had taken a few attempts in front of the camera to video the 4x4x4 robot performing a complete solve without jamming! I dreaded the thought of trying to shoot a video of close to double this length without a much more reliable mechanism. Finally, and perhaps more importantly from my personal perspective, just a step up from 4x4x4 to 5x5x5 didn't really seem like much of a challenge - maybe 6x6x6 would be more interesting?
So I spent a lot of time thinking about a new LEGO mechanism that could manipulate three different layers of a cube and do so much faster and with much greater reliability than the previous 4x4x4 solver. Then, as is often the case, a simple and "obvious" solution occurred to me. I conceived the "MultiCuber" design. Instead of turning the face or layers of the cube by lowering it into a "turntable", this new design works by lifting the cube up into a "cage" that turns it from above. This avoids the unreliable friction issue by allowing the cube to be supported from underneath on a "piston". It also allows any number of layers of the cube to be turned simply by raising the cube into the cage by an appropriate amount. Theoretically, this mechanism could be used to solve a cube of any size down to 2x2x2 and even above 6x6x6. The addition of a tilting mechanism underneath the cage allows the cube to be orientated so that any of the three axes are vertical so any layer can be turned. The whole mechanism is much simpler than the original 4x4x4 solver which included a differential to distribute the torque from one motor to both grip and lift the cube. As a result, I anticipated that the robot would perform moves much faster and more reliably than the previous 4x4x4 design.
All I needed was a cube...
I was aware that 6x6x6 cubes were readily available and also that it was possible to buy 7x7x7 puzzles. Strictly speaking these are V-CUBE puzzles rather than Rubik's Cubes. However, the 7x7x7 "cube" is not quite cubic - it has slightly curved faces. I believe this is a result of the small size of the corner pieces relative to the overall cube size and the internal mechanism that holds the puzzle together. My initial reaction was to dismiss the 7x7x7 as too difficult because of its curved surfaces, but I decided to buy one anyway. When the cubes arrived I set about building the "MultiCuber" mechanism of the appropriate size for the 6x6x6. But the 7x7x7 cube is a beautiful puzzle to look at and hold and I couldn't resist constantly picking it up and playing with it. It didn't take long for me to decide that it was worth an attempt at a 7x7x7 solver!
The curved surfaces of the 7x7x7 proved less of a problem than I anticipated. I expected that keeping the cube upright might be an issue but it transpires that the 7x7x7 cube naturally settles upright on the center of one of its faces, despite the curve, owing to the fact that the center of gravity is below the center of the radius of curvature (this reminded me of the "Weebles" that "wobble but don't fall down" - but you may well be too young to remember!?! ). The curved surfaces of the puzzle mean that layers are different sizes so at first I thought it would be tricky to turn them precisely. The top of the MultiCuber has a fixed square ring and a rotating square ring just above it at the bottom of the rotating cage used to turn a layer of the cube relative to the one directly beneath it. These rings are a fixed size, a little larger than the widest part of the curved cube so in order to turn a layer by the appropriate amount, the rotating ring is turned an extra amount to compensate for the different gap between the ring and each different layer of cube. The control software running on the LEGO Mindstorms NXT controller determines how much extra rotation of the cage is required to correctly align the layers depending on which layer is being manipulated.
I implemented the generic NxNxN solving algorithm configured for size 7x7x7 as an Android application on the DROID by Motorola smartphone. The increased processor performance (TI's OMAP 3630 based on the ARM Cortex-A8) and memory of this phone compared with the Nokia N95 used in the previous robots was important in supporting a set of large lookup tables resulting in a relatively short solution. I say "relatively" since it still takes around 500 moves to solve the 7x7x7 cube compared with about 100 for the 4x4x4. Even with the MultiCuber's faster mechanism, this was going to take around 40 minutes (at this point I was glad that Luke from our "demo" team designed the big LED timer that I described in my previous blog entry with two digits for minutes!).
We managed to shoot raw video footage of a complete solve one afternoon (if I recall correctly the robot did not jam at all during filming!) and then Scott took on the challenge of editing the forty minute solve into a three minute video. I'll let you judge for yourself how entertaining Scott managed to make the "marathon" solve!
So now this really must be the end of my series of ARM Powered LEGO cube solver creations (unless you have an intriguing suggestion)... or should I learn from experience this time?!?