How to make Prolog depth-first-search algorithm go deeper into the tree? (Applied to Sokoban)

Question

I'm trying to solve the Sokoban puzzle in Prolog using a depth-first-search algorithm, but I cannot manage to search the solution tree in depth. I'm able to explore only the first level.

All the sources are at Github (links to revision when the question was asked) so feel free to explore and test them. I divided the rules into several files:

• board.pl: contains rules related to the board: directions, neighbourhoods,...
• game.pl: this file states the rules about movements, valid positions,...
• level1.pl: defines the board, position of the boxes and solution squares for a sample game.
• sokoban.pl: tries to implement dfs :(

I know I need to go deeper when a new state is created instead of checking if it is the final state and backtracking... I need to continue moving, it is impossible to reach the final state with only one movement.

Any help/advice will be highly appreciated, I've been playing around without improvements.

Thanks!

PS.- ¡Ah! I'm working with SWI-Prolog, just in case it makes some difference

PS.- I'm really newbie to Prolog, and maybe I'm facing an obvious mistake, but this is the reason I'm asking here.

Answer 1

This is easy to fix: In sokoban.pl, predicate solve_problem/2, you are limiting the solution to lists of a single element in the goal:

   solve_dfs(Problem, Initial, [Initial], [Solution])

Instead, you probably mean:

    solve_dfs(Problem, Initial, [Initial], Solution)

because a solution can consist of many moves.

In fact, an even better search strategy is often iterative deepening, which you get with:

    length(Solution, _),
    solve_dfs(Problem, Initial, [Initial], Solution)

Iterative deepening is a complete search strategy and an optimal strategy under quite general assumptions.

Other than that, I recommend you cut down the significant number of impure I/O calls in your program. There are just too many predicates where you write something on the screen.

Instead, focus on a clear declarative description, and cleanly separate the output from a description of what a solution looks like. In fact, let the toplevel do the printing for you: Describe what a solution looks like (you are already doing this), and let the toplevel display the solution as variable bindings. Also, think declaratively, and use better names like dfs_moves/4, problem_solution/2 instead of solve_dfs/4, solve_problem/2 etc.

DCGs may also help you in some places of your code to more conveniently describe lists.

+1 for tackling a nice and challenging search problem with Prolog!