For their final project for ECE 5760 at Cornell, [Alex], [Sungjoon], and [Rameez] are solving Rubik’s Cubes. They’re doing it with an FPGA, with homebrew robot arms to twist and turn a rainbow cube into the correct position.
First, the mechanical portion of the build. The team are using a system of three robot arms positioned on the left, right, and back faces of the cube relative to a camera. When a cube is placed in the jaws of this robot, the NTSC camera data is fed into an FPGA, where a Nios II soft core handles the actual detection of the cube faces, the solver algorithm, and the controller to send servo commands to the robot arms.
The algorithm used for solving the cube is CFOP – solve the white cross, the white corners, the middle layer, the top face, and finally the entire cube. In practice, the robot ended up taking between 60-70 moves. This is not the most efficient algorithm; the Thistethwaite algorithm only requires 52 moves. There’s a reason for this apparent inefficiency – the Thistlethwaite algorithm requires large look-up tables.
Once the cube is scanned and the correct moves are computed, the soft core in sends commands out through the FPGA’s GPIO pins. Each cube can be solved in under three minutes after it has been scanned, but the team ran into problems with scanning accuracy. It’s a problem that can be fixed with the right lighting setup and better aberrant cubie detection, and a great final project using FPGAs.
Video demo below.
I got all excited when I saw this thinking that the solving logic was done in HDL/FPGA. But no just a boring soft core using an everyday algorithm.
The rubic cube is a state machine so it would be great to see HDL that emulates that state machine directly in logic ie no CPU or tables. It would give the shortest and most direct or ‘exact’ solution. ie If you made 7 moves to mix it up then it would solve by reversing those seven moves without knowing what they were.
Well I will just have to learn HDL and do it myself.
Even the servos has built in controllers. Maybe a case of ‘you must use an FPGA’ for the course. Pretty good writeup if you ignore the FPGA bit.
I think some calculations done on supercomputers concluded that without knowing the mixing movements for the cube the best number of movements one can expect to use in order to solve it would be 20 or something.
Almost, the MAX number of moves any perfect solution can take is 20. The lower bound is 1 move.
I suspect that finding the optimal move sequence would require huge amounts of pre-computed tables.
Just a matter of time until FPGAs are filled up with jQuery.js soft cores :-(
I’m not 100% sure, but I think in this case it’s “A” instead of “AN”.
The F in FPGA is pronounced with a vowel sound (“eff”), so “AN” is correct.
*an initial vowel sound…. even
Thanks! Not wanting to troll, wanting to learn. I thought in my head “A fire extinguisher… or An fire extinguisher.” without thinking that saying the letter is actually different than using it in a sentence. Thanks for helping me learn a new thing today.
Just like how ghoti is pronounced fish!
Holy hell. I was trolling the grammar nazis with, “The team are…” in this post. You chose, “an FPGA”??? What is wrong with you?
//man hackaday’s really gone downhill the people complaining about the grammar can’t even get it right anymore.
Good one Brian! :D
I’d say “the team are”, since I see it as being a team of people. Like a gaggle of geese or whatever. Maybe those bigshots in Dictionary Town would disagree, but I’ve been getting sicka their crap recently.
“Team is” vs. “Team are” is a British/American thing, which is kinda cheaty as far as trolling goes. A better one would be Whoppers junior.
Well “an FPGA” is technically correct. Abbreviations are handled phonetically rather than literally. God this language is awful why couldn’t we get the Russians to invade. Their language isn’t broken like ours.
I’d rather have a German invasion. I’ve always fancied compound nouns. (c: