Can a GA be made that can slove Rubics Cubes? Are there other ways to solve the problem? Thanks.

[google]

Quote: Original post by daniel_i_l
Can a GA be made that can slove Rubics Cubes? Are there other ways to solve the problem?
Thanks.

Yes, there are a LOT of better ways than GA to solve that class of problems. Google it as suggested, but I believe a simple A* might do the trick.

Edit: Screw that. A* WILL do the trick.

Could you explain how A* could be used here? Mainly, how do you get the hueristic?
Thanks.

Quote: Original post by daniel_i_l
Could you explain how A* could be used here? Mainly, how do you get the hueristic?
Thanks.

Well, you should be a carpenter, 'cause you hit the nail on the head! While getting an admissible heuristic should not be too difficult, finding a "good" AND admissible heuristic seems tricky. Honestly, Im terribly bad with rubik cubes. A simple one should be to add the sum of 8 minus the maximum of similar colors for each side, minus one. For example, if all colors on a side are different, you get 9-1 = '8' for this side. If you have 3 blue, 2 red and 4 yellow, you get 9-4 = '5' for this side. Then add for all sides.

If we want an optimal solution, we have to make sure our heuristic is admissible. Each 'move' can change 12 tiles. In the best case, all those tiles will move from misplaced to well-placed. Which should decrease our heuristic by at most 12... I think. (might want to verify that). So if we set the cost of one move to '12', and if Im not drunk right now, that would make our heuristic admissible.

Quote: Original post by daniel_i_l
Can a GA be made that can slove Rubics Cubes? Are there other ways to solve the problem?

GAs are vastly overrated in general and, for the problem of Rubik's Cube, would be completely the wrong tool. Indeed, GAs are almost never the right tool for any job.

There has been a few academic papers on solving Rubik's Cube. Notable are those by Richard Korf; see this UCLA announcement from back when:

http://www.seas.ucla.edu/hsseas/press/1997/korfcube.html

See also Korf's work on IDA* and macro operators (which relates to his Rubik's Cube paper).

If you're interested in solving the cube (as opposed to solving it optimally) you can resort to concepts from mathematical group theory for constructing move sequences. This sounds more complicated than it is, and I've pasted below an article that I posted to comp.graphics.algorithms some while ago on that particular topic:

--- start snip ---
From: Christer Ericson <christer_eric...@NOTplayTHISstationBIT.sony.com>
Newsgroups: comp.graphics.algorithms
Subject: Re: Basic matrix hierarchy queston
Message-ID: <MPG.1b3e3b196a44ea2598976a@news.verizon.net>
Date: Sat, 19 Jun 2004 20:01:55 GMT

In article <d6f8d093g84sdlpb5hqr89hr1r43hqf...@4ax.com>, nobody-
h...@mac.com says...
> On Fri, 18 Jun 2004 22:13:18 +0000 (UTC), dkco...@panix.com (David
> Combs) wrote:
> >Am I right (or wrong) to recall that this transform-doSomething-untransform
> >concept occurs throughout math, even in group theory? Perhaps you
> >can say something general about it, that spans all the uses?
>
> Nothing jumps out at me "thoughout math", but certainly, yes, in group
> theory and linear algebra.

In group theory, the "transform-doSomething-untransform" is known as
a conjugation. A particularly illustrative example of the group
theoretic concepts of conjugation (and commutation) is the effect of
move sequences on a Rubik's cube.

If P and Q are two arbitrary move sequences, then PQP' is the
conjugation of P and Q, where P' denotes the inverse of P, that is,
the move sequence backwards.

Let L, R, F, B, U, D denote the left, right, front, back, up, and
down faces of a Rubik's cube. Thus the front, right, upper corner
cublet is the FRU cublet. Let the letters also denote a clockwise
turn of that face when viewed face on. A clockwise turn is the
inverse of these, so e.g. F' is a clockwise turn of the front face.

Now, to see how conjugation is useful, consider having a move sequence
Q that, say, flips the UF and UR edge pieces. However, what you
really want is to flip the UL and UR edge pieces. So, what you do
is apply the move sequence P = LF before performing Q, which brings
the UL piece into the UF position. You now apply Q. Then you perform
P' = (UF)' = F'U' to move the UL piece back into its place (and
unscrambles everything else that happened when you performed P).

In other words, if you have a move sequence Q that flips some given
two edge pieces, you can through the conjugation PQP', for different
move sequences P, flip _any_ two edge pieces of cube!


The question then is, how do we flip two edge pieces in the first
place? You can create a move sequence for this through the concept
of commutation, where given move sequences P and Q, PQP'Q' is their
commutation.

First, lets come up with a move sequence P that flips an edge piece
of the U face, but otherwise leaves the U face intact. Some
experimentation will show that P = R'U'DBBUUD'D'F' accomplishes
this (middle layer moves can accomplish the same thing faster,
but I'm ignoring these here).

After P you have the UF edge piece flipped, the U layer otherwise
intact, and the rest of the cube seemingly scrambled. If you now
did P backwards (P') the cube would unscramble.

So before doing P', you do Q = U, which brings the flipped UF
piece to UL, and the unflipped piece at UR to UF. Now doing P'
will flip the piece at UF and unscramble everything else that
was scrambled. All left to do after performing PQP' is to do
Q' to restore the twist we did of the U face, and you'll have
two flipped edge pieces.

Using PQP'Q' commutations, you can create any move sequence you
desire.

Together, conjugations and commutations will form all the
move sequences to solve Rubik's cube (in any of its sizes)
plus any other similar toy puzzle, like e.g. the 15-puzzle.

How neat it is that people playing with a Rubik's cube are
implicitly dealing with group theory doing so! :)
--- end snip ---

You can search for the sequences that do things like "flips an edge piece
of the U face, but otherwise leaves the U face intact" using e.g. the IDA* algorithm that Korf describes, or any other basic search algorithm (breadth-first, branch-and-bound, etc). If you're not familiar with these algorithms, they are described in detail in most introductory AI textbooks.