CV Rubik - Computer sees Rubiks cube and solves it

CV Rubik is a C++ application that solves a 3x3 Rubik's cube. It uses a webcam to "look" at a Rubik's cube and generate a step by step solution in 3D graphics.
CV Rubik draws on knowledge from different fields of computer science such as Computer Vision, Artificial Intelligence and 3D Graphics.
djsunkidsays...

i love this, but one complaint. Whatever algorythm they are using to solve the rubiks cube seems really bad. I've definitely seen much more optimised ones. There is no way you need that many steps to descramble a 3x3.
...
a little searching and i found this:

I generated 1 million random cubes on a 3 GHz Pentium 4 PC, trying to find a cube which was not solvable within 20 moves with the Two-Phase-Algorithm. This cube then would be a test candidate for a position which would need at least 21 moves to be solved with God's Algorithm.

But the Two-Phase-Algorithm solved all generated random positions within 20 moves. More precisely, it solved about 30000 random cubes per hour and the final distribution of the maneuver length was:
13: 4, 14: 18, 15: 81, 16: 609, 17: 3893, 18: 23411, 19: 141366, 20: 830618.

This shows, that the probability to find a random cube position which cannot be solved within 20 moves with the Two-Phase-Algorithm in a reasonable time must be very low or zero.
It also shows: If there are any cube positions which need at least 21 moves to be solved, these positons are very rare and there is almost no chance to find such positions by random.


So yes, there are definitely much, MUCH better ways of solving any given rubik's cube, especially for a computer.

This "two-phase" algorythm may be difficult or impossible for a human to learn, it may involve impractical memorisation, or something, but you can download a version from that site.

So yeah, awesome stuff, but they should implement whatever this "two-phase" business is.

Send this Article to a Friend



Separate multiple emails with a comma (,); limit 5 recipients






Your email has been sent successfully!

Manage this Video in Your Playlists




notify when someone comments
X

This website uses cookies.

This website uses cookies to improve user experience. By using this website you consent to all cookies in accordance with our Privacy Policy.

I agree
  
Learn More