In this exercise we will solve a sliding puzzle using iterative deepening depth-first search1. The following code implements this principle in Prolog (and prevents cycles).

solve(A, Solution) :- between(1, 25, I), solve(A, [A], I, Solution), !.

solve(_, _, 0, _)                   :- !, fail.
solve(State, Solution, _, Solution) :- goal(State), !.
solve(State, Visited, D, Solution) :-
    successor(State, NextState),
    \+ member(NextState, Visited),
    D1 is D-1,
    solve(NextState, [NextState|Visited], D1, Solution).

You must still write the successor/2 function that transforms a current state into a possible next state.

Representation

4 by 4 puzzle with values from top to bottom left to right: 15, 2, 1, 12, 8, 5, 6, 11, 4, 9, 10, 7, 3, 14, 13

The puzzle is represented as an array of positions: [PosEmpty, Pos1, Pos2, Pos3 | ....]. Where each position is represented as a tuple of the row and column joined by a /, counting from one left to right top to bottom.

The example image would thus be represented as:

4/4,1/3,1/2,4/1,2/2,2/3,3/4,2/1,3/2,3/3,2/4,1/4,4/3,4/2,1/1

Your implementation of successor/2 should hold when the board in the first argument can be converted to the board in the second argument by sliding one of the pieces adjacent to the hole (head of the list) in the hole.

Usage

To test your code, you can use this database2 it contains the solve/2 predicate from above and a goal/1.

Note: Iterative deepening depth-first search has a time complexity of \(O(b^d)\) where \(b\) is the branching factor (that is, the amount of solutions successor/2 returns at most) and \(d\) is the depth of the first solution. A better approach for this problem is A*-search.