Android phone solves Rubik’s cube in 12.5 seconds
Last updated Nov 11, 2010 — 38674 views
A Lego Mindstorms robotics kit controlled by an HTC Nexus One smartphone successfully untangled a Rubik’s Cube puzzle in 12.5 seconds at this week’s ARM developer conference in Silicon Valley.
For those unfamiliar with ARM Ltd., it’s the company that created the popular ARM RISC CPU architecture employed in billions of smartphones, set-top-boxes, web-tablets, and numerous other consumer devices.
ARM principal engineer David Gilday, who masterminded the robotic Rubik’s Cube demo, told DeviceGuru that the 12.5-second run was the fastest result at the show, but that the average 3x3x3 Rubik’s Cube solution in the current setup had been running around 15 seconds.
Here’s a YouTube video showing Gilday demonstrating his latest 3x3x3 cube-solver:
3x3x3 cube solver run by an HTC Nexus One
In the above demo, the cube-solving software runs on an HTC Nexus One, which is powered by Android 2.1 running on a 1GHz Qualcom QSD8250 “Snapdragon” processor along with 500MB of system RAM.
Like all of Gilday’s robotic cube-solvers, the Nexus One’s Snapdragon processor is based on an ARM CPU core, which of course is why he gets to build and play games on his employer’s nickel. (In fairness, he probably does most of it on his own time.) On the other hand, these days its difficult to find a smartphone that’s NOT running ARM CPU technology.
The current 3x3x3 cube-solver’s 15-second average represents a substantial improvement over the 25-second solutions of an earlier version, which was powered by a circa-2006 Nokia N95 smartphone. Gilday attributes the improvement to the combination of a faster CPU, increased RAM, and revamped cube-solving code. (The earlier version’s controlling smartphone had a 332MHz ARM11360-based TI OMAP2420 processor and 64MB RAM; watch a short video demo of that one here.)
From 3x3x3 to 7x7x7, and beyond
In a post on ARM’s blog, Gilday reflects on the 18-month process of enhancing his robotic cube-solver setup so that it could solve more complex cube puzzles. “Strictly speaking,” he notes, these are called V-Cubes, rather than Rubik’s Cubes.
“While demonstrating [the 3x3x3 cube-solving] robot to a few colleagues at ARM, I had some other puzzles lying on the desk including 4x4x4 and 5x5x5 Rubik’s Cubes,” recalls Gilday in one of his blog posts. “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 [a colleague] suggested a way of adapting the original mechanism to allow the second layer to be manipulated.”
To prepare for solving more complex cubes, Gilday developed a generalized, table-driven software algorithm that enabled “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.”
“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,” he explains. “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.”
Gilday then set about porting the original smartphone application from the Nokia smartphone’s Symbian S60v3 OS to Android, and modifying it so that it could solve cubes of arbitrary size. Since the Nokia app had been coded in Java using MIDP 2.0, the port to Android went smoothly, he notes.
Gilday next modified the mechanical design to handle 7x7x7 sized cubes, implemented a 7x7x7 variant of the generic NxNxN algorithm as an Android application on the Motorola Droid smartphone, and tested the setup. It took the robotic solver about 500 moves to solve the 7x7x7 puzzle, with an average time-to-solution of about 40 minutes.
Here’s a YouTube video showing the Droid-based setup solving the 7x7x7 puzzle:
7x7x7 cube solver run by a Motorola Droid
In terms of racing humans, Gilday says the Lego robotics kits can only manage around 1.5 moves per second, whereas human players can make between 5 and 6 moves per second, amazingly enough.
Further information
For more background on Gilday’s robotic Rubik’s Cube solver project, read his complete blog post, here. For further information on ARM Ltd. and its ARM architecture processor technologies, visit the company’s website, here. Information on the Lego Mindstorms Robotics Kits may be found here.
Two other Rubik’s Cube solving robots are described in these DeviceGuru posts:
I was half expecting an Arduino to be hanging off that build somewhere. Nice project.