| From: | David McMinn |
| Date: | 25 Aug 2000 at 16:50:55 |
| Subject: | Re: rubik's cube |
Hi pbrace@cwctv.net
> Does anybody have any idea how to write ablitz program to solve a Rubik's cube.
> apart from working out that there are 18 possible moves and the total number of
> positions is in the region of 20 digits long the only thing I can think of is a
> loop trying it first in one move. However with this method the total amount of
> moves goes up by a factor of 18:
>
> Moves Total number
> 1 18
> 2 324
> 3 5832
> 4 104996
> 5 approx 1.8 million
>
> This leads to the proram slowing down a lot. Prehaps it would be better in C
Perhaps it would be better to re-think how you're going to calculate the
solution. How many moves (roughly) does it take on average to complete a
Rubik's cube? 20 sounds like a fairly low estimate, but if we take it as an
example, you're going to have to evaluate 1.27x10^25 moves. Obviously you know
the starting state (otherwise you'd have to multiply the number of moves by the
number of starting states).
C, Blitz or ASM, that's gonna take a long time. Unless it only needs a low
number of moves (from your table, I'd say low would mean 4, 5 or not much more).
You might want to take a look at mathematical optimisation techniques and
perhaps some AI stuff. Genetic algorithms could be used, although it might be
tricky to get right and would still take a while. Expert systems could also be
used and would probably be quicker (they're based on sets of rules, so if you
get a Rubik's expert to give you some rules for solving it your program would
be quite good too).
---------------------------------------------------------------------
To unsubscribe, e-mail: blitz-list-unsubscribe@netsoc.ucd.ie
For additional commands, e-mail: blitz-list-help@netsoc.ucd.ie