I was floating around youTube and came across Rubot II, the rubiks cube solving robot. I thought that was amazing and have been looking in to writing my own program to solve the rubik's cube. Ive never actually been able to solve the cube myself :-P, so ive been browsing the net looking to solutions and algorithms to get me started. I came across a couple of websites that say they have written programs that can solve a random cube in as little as 17 - 19 moves. I dont believe it myself, the one i found that actually worked did it in 189 moves. Has anyone seen a program that can solve the cube that fast? Maybe on the net that i could check out. Thanks.

189 moves? That's crazy. Most likely it was following the traditional one face, middle, lower scheme. 189 is WAY out of the park.

Why so skeptical? Go to http://kociemba.org/cube.htm There you will find a fantastic program that will prove to you that a randomly scrambled Rubik's cube can be solved in as little as 18 moves. Moves being defined as the rotation of any face by 90 or 180 degrees - quarter or half turns. The author also goes into the math behind it all, but it is a little broken and hard to follow, I thought. Interesting, none the less.

The software will find an answer very fast that is usually around 20 moves or so. You can also search for an optimal solution that is often 18. For 1000 scrambled cubes, most were solve in 18 moves and I don't think any went over 19.

Let me know what you think once you've checked it out.

-Kirk

It was kind of hard to understand. It does work tho, im a believer. I dont think i can handle writing my own though. I didnt really understand what was going on. I did get a couple laughs out of it though, like "anti-clockwise". I think im going to pass on writing my own rubiks cube solver, for now at least. Ill wait until i get some more AI under my belt before taking on such a task. Thanks for the help!

What is significant about Rubot II is NOT that it can solve the Rubik's cube... that's been proven to be a trivial exercise. The true offering of this system is the visually servoed control and planning software behind it. Getting a robot to understand what it is looking at while it manipulates that scene is not an easy undertaking.

There are a number of videos of robots performing image capture before initiating a solution to the Rubik's cube. Here are some links:

(this one is Rubot v1)




The software I mentioned also has a webcam option that allows you to scan your cube rather than entering it in manually. Very cool stuff.

As for writing your own, I think that would be a great idea. As a start, you might try to solve the 2x2 cube rather than the 3x3. Look for things like breadth first search, and depth first search to get started. You would not want to use these techniques on a 3x3 cube as there are just too many possible states, but the 2x2 could be solved using breadth first search. Depth first search could solve it also, but you'll have to be a little more tricky in its use for this problem.

Once you've done the 2x2, you will have the experience to move to the next level of search techniques and the 3x3 cube. Iterative Deepening Search, Iterative Deepening A*, and Fringe Search would be the next set to consider.

Then, if you really want a challenge, try the 4x4 and 5x5. I'm not convinced an optimal solution to the 5x5 could be found. What are your thoughts, Timkin?

-Kirk

I havent ever looked at the popular Cube myself very much...

But I'm wondering, does solving it involve just a big Search algo? or is it more just a series of Rules and patterns to follow?
(this question applies both to the human expert's approach and the computer's, since I'd guess they do it differently.)

Solving the Rubik's Cube optimally - finding the shortest sequence of moves - is done by a heuristic search algorithm. There published algorithms that have solved it in ~18 moves use Iterative Deepening A*. I'm considering trying to do it myself using Fringe Search.

For humans, the main method is to solve one face with the edges correct, solve the middle layer, solve the bottom corners, and finally solve the bottom edges. This takes ~175-200 moves to do, which is FAR from optimal, but is easily remembered and interpreted by humans.

-Kirk

Quote:Original post by kirkd
There are a number of videos of robots performing image capture before initiating a solution to the Rubik's cube. Here are some links:

(this one is Rubot v1)

I wasn't suggesting Rubot II was the only bot to do visual servoing. Indeed, it's quite a common approach these days (although the camera is often in the hand)... it's just not an easy approach! ;)

Quote:
Then, if you really want a challenge, try the 4x4 and 5x5. I'm not convinced an optimal solution to the 5x5 could be found. What are your thoughts, Timkin?

The problem with solving Rubik's cube is the branching factor and the nonlinear nature of the plan space. The result is that a given state change can essentially be produced an infinite number of ways and there may be more than one 'shortest' path between any two states. I've seen good results on solving problems such as this using plan space search methods. This is something that operations research people do well.

As for finding an optimal solution to a 5x5, intuitively I don't see any reason why it can't be done, but certainly the complexity is now huge, so the feasibility of finding a solution has plummeted. One approach may be to solve 8 concurrent, overlapping corner problems, where the corners overlap (so corners on a 3x3 cube are three 2x2 faces). The coupling constraints would be that the corner does not violate colour overlap on each of its faces. While this might be an inefficient approach for 3x3, it might prove to be useful for larger cubes.

Cheers,

Timkin

Yes, the branching factor is a killer. You can reduce it somewhat by enforcing rules on face rotations. For the 2x2x2 cube, the branching factor is around 9 for the first move - 3 different rotational planes with 3 moves each. You can push that down to 6 for subsequent moves if you disallow sequential rotation in the same plane.

Similar techniuqes for the 3x3x3 go from 18 for the first move down to 15 for subsequent moves. Here you disallow sequential face rotations and enforce an order when you rotate different faces in the same plane. Always rotate the top first and the bottom second if both faces have to turn sequentially.

The best I can come up with for the 4x4x4 is about 30 - the same branching factor as chess. And the 5x5x5 comes in at around 40. YIKE!

I'm not familiar with plan space search methods. If you have a link to what you would consider to be a good review, I would greatly appreciate it. I haven't search CiteSeer or Google Scholar yet, but I'd certainly take your recommendation.

-Kirk