Every decade (or so), I’ve found occasion to go and re-learn Prolog, and it just happened again. If you aren’t familiar with the Prolog programming language, the best description I can give you is this – Prolog is a declarative programming language where you focus on describing the what, and not the how of arriving at a particular result.
Each time I re-learn Prolog, I start with the usual family tree, and three towers problem (Tower of Hanoi|Benares|Bramha|Lucas, …), and get to whatever I’m trying to do. Most of us view the three towers problem as an example of recursion, and there the matter rests.
Simply put, to move N discs from the left tower to the right tower, you first move the top (N-1) discs from the left tower to the middle tower, and then move the Nth disc to the right tower, and then move the (N-1) discs from the middle tower to the right tower. You can prove (a simple proof by induction) that the N disc problem can be solved in (2^n – 1) moves.
In prolog this would look something like this (sample code):
move(1, A, B, _, Ct, Steps) :-
Steps is Ct + 1,
write(Steps), write(': '), write('Move one disc from '),
write(A), write(' to '), write(B), nl.
move(N, A, B, C, Ct, Steps) :-
N > 1,
M is N - 1,
move(M, A, C, B, Ct, N1),
move(1, A, B, C, N1, N2),
move(M, C, B, A, N2, Steps).
towers(N) :-
move(N, left, right, middle, 0, Steps),
write('That took a total of '), write(Steps),
write(' steps.'), nl.
When you run this program, the output looks like this:
$ swipl -g 'towers(3)' -g halt recursive.pl
1: Move one disc from left to right
2: Move one disc from left to middle
3: Move one disc from right to middle
4: Move one disc from left to right
5: Move one disc from middle to left
6: Move one disc from middle to right
7: Move one disc from left to right
That took a total of 7 steps.
$But this kind of solution doesn’t really show an important aspect of Prolog, the ability to explore the problem space, and discover the solution. The recursive solution shown above can be implemented just as well in C or python.
In Prolog, you can implement the solution a different way, and only provide the system a set of rules and have it discover a solution. Here’s one way to do that.
Here we define a high level goal (towers/1) just as above.
towers(N) :-
findall(X, between(1, N, X), L),
reverse(L, LeftList),
towers(LeftList, [], [], [], State),
!,
showmoves(1, State).
But beyond that, the similarity ends. The implementation of towers/5 is totally different. It consists instead of seven rules.
At any time, there are one of 6 possible moves that one can make. Those 6 moves are to move the top disc from left, center or right, and move them to left, center, or right. That gives us left -> center, left -> right, center -> left, center -> right, right -> center, and right -> left. Each of those is a rule.
There’s the seventh rule to determine whether or not we’ve reached the desired end state.
Here’s an implementation of the check for the desired end state:
towers(Left, Center, Right, StateIn, StateOut) :-
done(Left, Center, Right),
StateOut = StateIn.
done([], [], _).
That’s it! The check to see whether, or not we are done is a single line of code. done/3 is called with Left, Center, and Right, and we’re done if Left and Center are empty and Right is something (what it is, we don’t care!).
The move from left to center (for example) looks like this:
towers(Left, Center, Right, StateIn, StateOut) :-
move(Left, Center, LeftOut, CenterOut),
State = [LeftOut, CenterOut, Right],
append(StateIn, [State], X),
towers(LeftOut, CenterOut, Right, X, StateOut).
That’s it! move/4 tries the move from Left to Center, and if it succeeds, we will record that state, and recurse. We record state so we can print the solution when we are done! You can see that towers/1 calls showmoves/2 which looks like this:
showmoves(_, []) :-
format('Done.\n').
showmoves(N, [H|T]) :-
format('State[~d]: ', N),
format('Left ~w, Center ~w, Right ~w\n', H),
N1 is N + 1,
showmoves(N1, T).
showmoves/2 is recursive and prints out the moves in order. The lovely thing about this program is that all it has is the rules to adhere to, that’s it. Here’s a simple invocation.
$ swipl -g 'towers(2)' -g halt rules_based.pl
State[1]: Left [2], Center [1], Right []
State[2]: Left [], Center [1], Right [2]
State[3]: Left [], Center [], Right [2,1]
Done.
When all the program knows is to follow the rules, it needs some help to prevent ending up in a cycle. Doing that just requires one more line of code in the towers/5 rule.
towers(Left, Center, Right, StateIn, StateOut) :-
move(Left, Center, LeftOut, CenterOut),
State = [LeftOut, CenterOut, Right],
\+ member(State, StateIn),
append(StateIn, [State], X),
towers(LeftOut, CenterOut, Right, X, StateOut).It doesn’t produce the ‘best’ solution, but it does produce valid solutions! The step (highlighted) is an example of one that is legal, but clearly wasted.
$ swipl -g 'towers(4)' -g halt rules_based.pl
State[1]: Left [4,3,2], Center [1], Right []
State[2]: Left [4,3], Center [1], Right [2]
State[3]: Left [4,3], Center [], Right [2,1]
State[4]: Left [4], Center [3], Right [2,1]
State[5]: Left [4], Center [3,1], Right [2]
State[6]: Left [4,1], Center [3], Right [2]
State[7]: Left [4,1], Center [3,2], Right []
State[8]: Left [4], Center [3,2,1], Right []
State[9]: Left [], Center [3,2,1], Right [4]
State[10]: Left [], Center [3,2], Right [4,1]
State[11]: Left [2], Center [3], Right [4,1]
State[12]: Left [2], Center [3,1], Right [4]
State[13]: Left [], Center [3,1], Right [4,2]
State[14]: Left [], Center [3], Right [4,2,1]
State[15]: Left [3], Center [], Right [4,2,1]
State[16]: Left [3], Center [1], Right [4,2]
State[17]: Left [3,1], Center [], Right [4,2]
State[18]: Left [3,1], Center [2], Right [4]
State[19]: Left [3], Center [2,1], Right [4]
State[20]: Left [], Center [2,1], Right [4,3]
State[21]: Left [], Center [2], Right [4,3,1]
State[22]: Left [2], Center [], Right [4,3,1]
State[23]: Left [2], Center [1], Right [4,3]
State[24]: Left [], Center [1], Right [4,3,2]
State[25]: Left [], Center [], Right [4,3,2,1]
Done.
Recall that the towers(4) problem can be solved in 15 moves (here’s what the recursive solution looks like:
$ swipl -g 'towers(4)' -g halt recursive.pl
1: Move one disc from left to middle
2: Move one disc from left to right
3: Move one disc from middle to right
4: Move one disc from left to middle
5: Move one disc from right to left
6: Move one disc from right to middle
7: Move one disc from left to middle
8: Move one disc from left to right
9: Move one disc from middle to right
10: Move one disc from middle to left
11: Move one disc from right to left
12: Move one disc from middle to right
13: Move one disc from left to middle
14: Move one disc from left to right
15: Move one disc from middle to right
That took a total of 15 steps.
While not the best solution, it is fascinating how prolog can find a valid solution with just the “what” and nothing about the “how”.
Complete code is here.
An issue described above is with the code producing sub-optimal results by moving the same disc in consecutive moves. A simple change to keep track of the last disc moved, and prevent it from being moved again. It didn’t have quite the expected results 😦
The first solution it finds is not great, but after a few tries it produces this (to explore alternater results, remove the cut on line 36).
State[1]: Left [4,3,2], Center [1], Right []
State[2]: Left [4,3], Center [1], Right [2]
State[3]: Left [4,3], Center [], Right [2,1]
State[4]: Left [4], Center [3], Right [2,1]
State[5]: Left [4], Center [3,1], Right [2]
State[6]: Left [4,2], Center [3,1], Right []
State[7]: Left [4,2], Center [3], Right [1]
State[8]: Left [4], Center [3,2], Right [1]
State[9]: Left [4], Center [3,2,1], Right []
State[10]: Left [], Center [3,2,1], Right [4]
State[11]: Left [], Center [3,2], Right [4,1]
State[12]: Left [2], Center [3], Right [4,1]
State[13]: Left [2,1], Center [3], Right [4]
State[14]: Left [2,1], Center [], Right [4,3]
State[15]: Left [2], Center [1], Right [4,3]
State[16]: Left [], Center [1], Right [4,3,2]
State[17]: Left [], Center [], Right [4,3,2,1]
Done.
Hype Cycles 