Hi, these are some instructions so you can enjoy my Sokoban solver if you
don't speak Catalan.
The applet requires a recent installation of a recent (1.3+, but get 1.4 for
best results) of the Java browser plugin, that you can get here.
Usage: the 'sokoban solver' button just displays an about box, the first drop
down lets you choose one of the bundled maps or the map editor (Editor de
mapes). The second drop down lets you choose the resolution method; manual
solver (you can use your keyboard cursors and 'u' for undo) and a configurable
tree search ('cerca d'arbre'). Clicking on the 'Som hi' button starts the
If you have chosen the tree search, the solver will ask you a few questions
to help you tailor the solve process:
- 'Tipus de situacio': it determines the node expansion performed by the
applet. 'Situacio Simple' means that it considers individual man movements and
'Situacio Complexa' works considering block pushes. In most cases, 'Situacio
Complexa' will solve the map faster, but the solution might be non-optimal in
regard to man-movements.
- 'Detectar blocs encallats' is 'stuck block detections'. If you choose
'si'/'yes', then the applet won't consider moving block to positions from
where a block cannot be pushed to a goal square. In most cases, enabling this
detection speeds up the process considerably.
- 'Ordre de la cerca': this chooses in which order the different movements
- 'Cost acumulat': this means the applet will process the possible
movements tree with a breadth first algorithm; it won't consider positions
at depth n until it has considered all up to depth n-1. This guarantees that
the solution will find will be that of the lowest depth (and thus will be an
optimal solution), but it's usually the slowest method
- 'Distancia minima als objectius': this means that the applet will
examine first the most 'promising' positions first (in regards to the chosen
heuristic), doing what is known as a 'best first search' algorithm. This is
usually the fastest method, but it returns non-optimal solutions.
- 'Cost mes distancia': this balances position depth and heuristics in
what's known as an A* search. If the heuristic fits some conditions, the
solution will be optimal. This is usually a little bit faster than 'Cost
- 'Tipus d'heuristica' lets you choose which heuristic function will be used
(if you have chosen an order which uses heuristics:
- 'Distancia de Manhattan Simple': the heuristic function is the sum of
each blocks Manhattan distance to the nearest goal square. This heuristic is
very simple and might get confused in very simple maps.
- 'Distancia en empentes': this heuristic function is the sum of the
minimum number of pushes needed to take each block to the nearest (in block
pushes) goal square. In some situations, this is slower than 'Distancia de
Manhattan Simple', but most of the time it is much better.