Rubiks Cube

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

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 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

I've been able to solve it many times with no more than 50 moves (probably less) but I couldn't tell if I was following some sort of method.

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

Quote:

Original post by kirkd 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

A good review... mmm, not off the top of my head. However, I do know a couple of people in this area... I'll look into it for you. If you're looking for articles though, I'd search the Operations Research literature, rather than the AI literature, since this is essentially a optimisation problem, but in operator (action) space, rather than state space (which most AI people work in). I'll see if I can locate some specific starting points for you.

Cheers,

Timkin

Excellent! Thank you, Timkin.

Quote:

Original post by ThreeDParadox 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!

I'm guessing your american, because it didn't say counter-clockwise :)

We say anti in the UK :)

Quote:

Original post by kirkdFor 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.

I agree on the method, but the number of moves is way out. I use a very slight variation of that method (I solve the bottom edges before the corners), and it comes in at around 100 moves. I know it's still inefficient, but it can still be done in about 55 seconds or so. Just thought it was worth a mention.