Ada-Sokoban-Solvers:

Usage -------------------------------------------------------------

command line:  <solvername> <puzzlefile> <lmax> <lnum>, where...
<solvername> is either "puller" or "ibox",
<puzzlefile> is the relative path to the puzzle file,
<lmax> is the maximum number of levels in file,
<lnum> is the level number to solve.

EG. ibox games/duPeloux_195.sok 195 2

=====================================================================

Brief Descriptions of some Algorithms Used --------------------------

The 2 sokoban solvers included are reverse breadth first searches 
that avoid storing partial traversals through tunnels.  That last fact
implies they are not strictly breadth-first searches, which, in turn,
mean the shortest solution is not a guaranteed result, unless one
counts moving through a tunnel as a single move.

Since these are reverse algorithms, the "pusher" becomes a "puller".

An article by Frank Takes shows clear advantages to working from
a solved position backwards to the start position, which prevents
deadlocked positions from taking up space in the search tree.
Puller-deadlocks are still possible, but they are less problematic 
because they self-terminate fairly quickly in a BFS.

These solvers avoid placing configs onto the search queue that represent
represent partial traversals thru tunnels.  Exceptions include 
a) if pulling and the box lands on a box-target;  or, 
b) if the puller lands on a puller-target = initial pusher position.

Written to be generic and robust, they could provide a platform
for experimenting with more specialized strategies.  As written, they 
have a size limitation of 127 valid interior box positions, and a 
maximum of 18 boxes.


================= puller, ibox =======================

I) "puller" (good for small, dense puzzles):
Puller centric => 
a) choose a puller direction to move;
b) choose whether or not to pull any adjacent boxes;
c) move 1 step.

II) "ibox" :
Inertial-Box-centric =>
a) choose a box;
b) choose a direction;
c) move the box 1 or more steps in that given direction;
d) store the box layout, but store only the puller corral...
	ignore the precise puller location.  The idea here is that
	once a solution is found, then the shortest puller path,
	within its corral, is deduced using dynamic programming.
e) Note that minimality of puller (pusher) moves is not guaranteed
	here because the choices made in a box-centric algorithm
	completely ignore the intermediate puller movements.


Three bookeeping techniques are used that I believe to be
commendable for their precision and speed:

1) a method for generating unique configuration search
	keys that account for puller-corral and box positions, 
	that, of course, must ignore box permutations.
	See type "keytype".

2) an efficient storage/access technique using a splay-tree 
	superimposed with a fifo-iterator.
	See splaylist.adb.

3) dynamic programming, also known as flood-fill, is very efficient
	for determining the puller-corral, and optimal puller-paths within 
	it, for a fixed box layout.

=======================================================================

Block-Slider Addendum (bfs.adb...breadth-first-search)

In BFS, the above utilities are also applied to solve the much simpler 
class of block slider puzzles (*.blok).

