> >non-optimal move
> define a non-optimal move....
>
> any optimal solution consists of optimal moves, no matter what those moves
> are or how counter-intuitive those moves are

I was playing with a 2x2 sloyed and calculating weights using a simple
scheme like the following.
+2_+1
+1__0_-1
___-1_-2

I can solve it in 15 moves, but at move #7 a peg moves from the middle back
to it's own side.
Temporarily decreasing the weight, but the very next move increases again.
So in that case, there is one non-optimal move that appears to be backward
using this particular weighting scheme.

I also don't think you have to search 86 levels deep.  You should go down,
and look for mirrors and flips of the boards you've already processed.  If
you find one, you know you can solve it the reverse of how you got to it.
Instead of keeping all boards, you could build a database (in memory, or
disk) of as many levels deep as you had storage room for.  Then instead of
searching 86 deep, you only have to search 86-(database level) deep.
Something tells me there's some solution out there, that goes 43 deep, and
then just reverses for the solve, assuming 86 is optimal which it probably
isn't.

Also you could compress the boards to 5 bytes.  4 bytes for one colors
position, and one byte to store the empty spots location.

AW

Post a reply to this message