Solving sliding puzzle with Prolog

This work has been created as my credit exam at subject Nonprocedural programming at MFF UK. It is about solving sliding puzzle with Prolog programming language.

Sliding puzzle on undirected graphs

Description of a problem

Let's say that we have undirected graph with n vertices marked with numbers from $[0, n-1]$ and also containing numbers from $[0, n-1]$. Let's call the vertex which contains $0$ a "zero vertex" or "empty vertex". Numbers are shifted betwen vertices using an empty vertex, it is, that contents of vertices $U$ and $V$ can be swapped, when there is an edge between them and one of them contains $0$.

The puzzle is solved, when the content of each vertex corresponds with it's mark.

Example: I have found a game (above), which is exactly the kind of the game we want to solve (it's author is Douglas Ensley, FlashAndMath.com). We can also solve Fifteen puzzle using this model.

Wilson's research (1974)

  • only for non-separable graphs
  • generally unsolvable for theta0 and polygons
  • bipartite graph (e. g. "grid" in 15 puzzle) - solvable only for even permutations
  • solvable in all other cases

Solving algorithm

We solve this by trying all possible moves (depth-first search), but only until we reach previously defined depth. In each step we decide the best next move according to heuristics.

Heuristics

Let's define a home distance of vertex $v$ as a length of the shortest path from mark of $v$ to it's content, which means, the smallest amount of moves to get it "home". Let's define a disharmony of a graph as a sum of home distances for all vertices. The puzzle is solved, when disharmony goes down to zero. If we have more moves possible from zero vertex, we choose them according to their influence on graph's disharmony. Firstly, those which make it smaller, then, those which don't change it and lastly those, which make it bigger.

Some comments about my implementation

  • For computing the shortest distances in a graph, I use Floyd-Warshall's algorithm.
  • For sorting vertices I use Insertion sort.
  • I don't allow the cycles of length 2 in the solution (E. g., when looking for solution up to 10 moves long, and one solutions is [1,2,3,4], then I don't return [1,2,1,2,3,4], although it is the right solution and it is only 6 moves long.

Source code in Prolog

Short documentation for my program

Input

Input graph can be defined anywhere in the code using this predicate
graph(Name, g(V, E)). 
Name means the name of this graph, we will access to it with this name V is the list of vertices in this form
[mark-content, mark-content, ...]
E means the list of edges in this form
[e(mark, mark), e(mark, mark), ...]

Example

graph(square,  g( [0-1, 1-2, 2-3, 3-0],  
                [e(0,1), e(1,2), e(2,3), e(3, 0)] ) ).

Which means this graph

Starting the computation

Výpočet se spustí predikátem
solve(Name, Max-moves).
  • Name is the name of a graph, inserted in predicate "graph"
  • Max-moves is the top limit of moves, which can be performed

Output

The output of my program are all possible lists of moves, which satisfy the specified "max-moves". They look like this
[vertex, vertex, vertex, ...]
"vertex" is the mark of vertex, which should swap it's content whith a zero vertex. Moves are sorted from left (first one) to right (last one). If you don't like the solution, you can generate another one by pressing ";". For our sqare from above, the solution is
[2, 1, 0]
As well as this
[0, 1, 2, 3, 0, 1, 2, 3, 0]

Already inserted graphs

For testing purposes, I already inserted some graphs from a game above and you can ask the program about their solution. These graphs are: graph1, graph3, graph5, graph7, graph9, graph11, graph17, graph30. For example, try putting

?- solve(graph1, 8).

Shortest solutions of puzzle from above

I inserted some puzzles from above into my program and this is the output. If you want, you can insert another ones, 15 puzzles or anything you want to solve.

NumberSolution
1 [2,4,3,2,1,0], [2,3,4,2,1,0], [1,2,4,3,2,0], [1,2,3,4,2,0]
3 [4,3,0,2,1,0], [4,3,0,1,2,0], [3,4,0,2,1,0], [3,4,0,1,2,0], [2,1,0,4,3,0], [2,1,0,3,4,0], [1,2,0,4,3,0], [1,2,0,3,4,0]
5 [3,2,1,0,3,4,1,0], [1,4,3,0,1,2,3,0]
7 [5,4,1,2,5,4,1,0], [5,2,1,4,5,2,1,0], [1,4,5,2,1,4,5,0], [1,2,5,4,1,2,5,0],
9 [1,5,2,3,4,5,6,0]
11 [5,4,1,2,5,4,1,0], [5,2,1,4,5,2,1,0], [1,4,5,2,1,4,5,0], [1,2,5,4,1,2,5,0]
17 [1,2,5,4,3,2,1,0,5,4,3,2,1,0]
30 [7,6,3,2,7,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,3,2,7,0]

Old comments (closed because of spam)