Re^3: Block-sliding puzzle

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.

Comment on Re^3: Block-sliding puzzle

Replies are listed 'Best First'.
Re^4: Block-sliding puzzle by tempest69 (Initiate) on Nov 20, 2009 at 05:37 UTC
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"; [download]	[reply] [d/l]

Replies are listed 'Best First'.

Re^4: Block-sliding puzzle
by tempest69 (Initiate) on Nov 20, 2009 at 05:37 UTC


#!/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";
[download]

[reply]
[d/l]