rfrfrf / javasokosolve Goto Github PK

When creating an issue, press the CC textfield and click in all our names. In 
that way we should all get an email notifying us that a new issue has arrived!

Deadlock detection should be improved. Currently, a deadlock is only detected 
if a box is in a corner. Pushing the box to a wall from which it cannot be 
removed again is not detected, for example, as well as pushing multiple boxes 
together etc.

Fixing this will probably significantly improve speed for some levels.

I think the best approach would be to create a map of "dead" tiles. A tile is 
dead if pushing a box there always means loosing the level. This map should 
only include the tiles that are always deadly, i.e. corners and tiles touching 
certain walls. Once we have this map (detecting which tiles touching walls are 
dead might be quite hard), we can use it in canMove instead of floor[][]. 

An example of a dead tile would be the center in the topmost reachable row in 
the first "classic" level, marked here with X - you cannot get the box out 
there, and you cannot push it to a target:
    #####          
    # X #          
    #   #   

However, the ones marked with X here:
       #####
  ######   #
  #   X    #
  #        ######
  #   X      ...#
  ###############
are NOT deadly tiles as a box placed there can be pushed out or to a target! 
(the tiles touching the left wall are dead)

This will take care of avoiding dead tiles, but there still needs to be a 
detection for "dynamic deadlocks" like this:
  ###############
  #  $         .#
  #      $$   ..# <-- these two boxes cannot be moved
  ###############
This will be very hard - if NO box can be moved, this is obviously already 
covered. However, we should also have a detection for "box cannot be moved and 
it never will become possible" (with the second part being the problem). 
Probably, we need to build some sort of depencendy graph ("box A can be moved 
only if B is moved first") and then detect circles, or doing a slightly simpler 
check "box A can be moved only if B is moved first -> check if B can be moved 
assuming A static".

Maybe we can check by creating clones of the board with just a subset of the 
boxes. Please check if the following assumption holds:
 1. Let b' be a clone of b with some of the boxes removed
 2. If b' has
      a) at least one box, and
      b) none of the boxes can be moved, and
      c) at least one box is not on a target, it means
     --> b is not solvable

If we miss some deadlocks it is OK, the solver will just be a bit slower. 
However, incorrectly classifying situations as deadlocks that are none means 
levels could become unsolvable. Therefore all deadlock detection code needs to 
be checked thoroughly and should be reviewed.

An overview of possible deadlocks can be found at 
http://sokobano.de/wiki/index.php?title=Deadlocks

The solution given by the solver is a sequence of box moves.

Input: Board, List<Move>
Output: String like "UULLDUURR"

In rev. 20, a "release candidate" for the midterm milestone was created and 
tagged as MidtermMilestone_RC1. The contents of the source folder have been 
zipped, successfully tested on my.nada.kth.se and are ready for submission from 
my point of view. Please check if you consider the code to be OK for upload to 
Bilda as our Midterm Milestone submission, and confirm here if you are.

--Jan

P.S.: Please ignore the branch path, google forces you to set one.