Re: Block-sliding puzzle

[Anonymous Monk]

Interesting. Is there any better algorithm compared to brute-force? Can we predict number of moves in advance? How about genetic algorithms?

[ambrus]

If you run this for larger boards (say 13 or 15, which takes quite some time) then you can easily see the general pattern of solutions you get (7n-3 steps for board size 2n+1 or 2n+2). You could write a program that generates that solution, that way you'd get a simple program to generate a solution that's quite good. If you actually wanted to prove that that solution is optimal, I don't know an algorithm that's much better than this brute force one. You could of course optimize this brute force solution to run a few orders of magnitude faster if you really needed to run it for large boards.

[tempest69]

It looks like the optimal solution is kinda straight forward. while I realize it's isomorphic I'm going to frame it in a static form. Step 1 is to move the B( corner uniq ) along the side. down assuming the upper right B position. C which blocked B can loop to the other side of B in 3 moves. B and C can continue until either B or C reaches the N/2 -1 position (below the center). We will now call B the one in position, c is now the other. Then B crosses Horizontally to the A column, A moves down, C moves up (to corner), B horizontally to C's column. C moves down.

now A and C are in vertical position. A at the edge A must now take 3 moves to the other side of C, using B as a stopBlock. then C and A continue taking turns of three to inch tward the horizontal center until the goal state is reached. There might be a trick to handle moving up the sides a bit more efficiently.. but the horizontal steps are pretty well stuck.

[tempest69]

I popped up some code. It's wastes a few moves somewhere.. and I havent tried it on even values, as the center has more cases. So non optimal code, but the runtime is very predictable, and near optimal for odd sized boards. And yes the Iso stabilization is a bit cheap. but it's a proof o'concept.

#!/usr/bin/perl
#

$max=44;
$moves=0;
%boardx;
$boardx{'A'}=0;$boardy{'A'}=0;
$boardx{'B'}=$max;$boardy{'B'}=0;
$boardx{'C'}=$max;$boardy{'C'}=$max;
$boardx{'Z'}=$max;$boardy{'Z'}=$max;
sub collide{
        if ($boardx{'Z'} <0){ return 1;}
        if ($boardy{'Z'} <0) {return 1;}
        if ($boardx{'Z'} >$max){ return 1;}
        if ($boardy{'Z'} >$max){ return 1;}

        if  (($boardx{'Z'}==$boardx{'A'})  && ($boardy{'Z'}==$boardy{'
+A'}))  {return 1;}
        if  (($boardx{'Z'}==$boardx{'B'})  && ($boardy{'Z'}==$boardy{'
+B'})) { return 1;}
        if  (($boardx{'Z'}==$boardx{'C'})  && ($boardy{'Z'}==$boardy{'
+C'})) { return 1;}
        return(0);

}

sub printBoard{
        print "\n";
        for($i=0;$i<=$max;$i++){

                for($j=0;$j<=$max;$j++){
                        $zed=1;
                        foreach ('A','B','C'){
                                if (($boardx{$_}==$j) && ($boardy{$_}=
+=$i)){
                                        print $_;
                                        $zed=0;
                                }

                        }
                        if ($zed){ print '.';}
                }
                print "\n";
        }
}
sub move{
        $block=shift(@_);
        $dir=shift(@_);# 0-3 nesw or urdl
        $boardx{'Z'}=$boardx{$block};
        $boardy{'Z'}=$boardy{$block};
        if ($dir==0){$boardy{'Z'}--;}
        if ($dir==1){$boardx{'Z'}++;}
        if ($dir==2){$boardy{'Z'}++;}
        if ($dir==3){$boardx{'Z'}--;}
        if (&collide){$moves++; return;}

        $boardx{$block}=$boardx{'Z'};
        $boardy{$block}=$boardy{'Z'};

        &move($block,$dir);
}
sub dinkUp{
        #assumes An A-left B left, C right Low
        &move('A',1);
        &move('B',0);
        &move('A',3);
        &move('B',2);
        &move('B',1);
        &move('A',0);
        &move('B',3);
        &move('A',2);
}
sub dinkSide{
        #assumes An A-left , C right , b RIGHT LOW
        &move('C',3);
        &move('A',0);
        &move('A',1);
        &move('A',2);
        &move('A',3);
        if ($boardx{'A'}==$max/2){return;}
        &move('C',0);
        &move('C',1);
        &move('C',2);
}


&printBoard;
&move('B',2);
&move('B',3);
&move('A',2);
&printBoard;
while ($boardy{'A'} > $max/2+1){
        &dinkUp;
}
if ($boardy{'A'}==$max/2){
        &move('C',0);
        &move('B',1);
        &move('C',2);
}

if ($boardy{'A'}>$max/2){
        &move('C',0);
        &move('A',1);
        &move('C',2);
        &move('B',0);
        &move('A',3);
        &move('B',2);
}
## ISO-STABILIZATION

&printBoard;
print "Isoform:\n";
$boardx{'A'}=0;$boardy{'A'}=$max/2;
$boardx{'B'}=$max;$boardy{'B'}=$max/2+1;
$boardx{'C'}=$max;$boardy{'C'}=$max/2;
&printBoard;
while ($boardx{'A'} < $max/2-1){
        &dinkSide;
}
if ($boardx{'A'}<$max/2){
        &move('C',3);
}
&printBoard;
print "moves: $moves\n";