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.
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
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.
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.
Short documentation for my program
InputInput 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), ...]
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 computationVýpočet se spustí predikátem
- Name is the name of a graph, inserted in predicate "graph"
- Max-moves is the top limit of moves, which can be performed
OutputThe 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.
|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]|
|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],|
|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]|