Re: [QUIZ] Perl 'Hard' Quiz of the Whatever #2008-12-28 - Symmetric Sokoban

Ron Isaacson wrote:
> 
> There are a few minor optimizations made at each step, like not
> putting the puzzle into any state it's been in before

Oops, and I found a bug in that logic. It's not just an optimization;
some kind of state cache is necessary to avoid just pushing the same
block back and forth forever. However, the cache currently ignores the
position of the player.

THAT is an optimization; given these two boards:

  A) #######   B) #######
     #     #      #     #
     # $ $ #      # $   #
     #     ###    # $   ###
     #     ..#    #     ..#
     #########    #########

There are multiple sets of pushes that will get you from A to B, and
no reason to try more than one set that gets you to the same result.
No matter where the player is once you've entered state B, the
possible future moves from there are all the same.

HOWEVER, if you take blocking into account:

  C) #####     D) #####
     #   #        #   #
     # #$#        # #$#
     # # ###      # # ###
     # $@..#      #@$ ..#
     #######      #######
    
States C and D are NOT equivalent -- one is solvable, and one isn't!
So if you ignore the position of the player entirely, that leads to
some valid (and possibly essential) moves being ignored.

I tried a quick fix, to add the player position to the state cache,
but that adds an order of magnitude to both the time and the number of
pushes in the solution.

What you really want is to consider C above equivalent to E below:

  E) #####
     #   #
     # #$#
     # #@###
     # $ ..#
     #######

because the available pushes from there are the same, but you don't
want to consider C or E equivalent to D.

--
Ron Isaacson
Morgan Stanley
ron.isaacson-/PgpppG8B+R7qynMiXIxWgC/[email protected] / (212) 276-1144