Day 3 of Prolog in Tate's Seven Languages in Seven Weeks focuses on solving constraints using Prolog; in particular constraints over finite domains. The author walks you through solving a Sudoku in Prolog, in what turns out to be a rather small amount of code. I didn't find the exercises in this section terribly interesting as they mostly involved extending the example provided in the book (e.g. solving a 6x6 Sudoku rather than a 3x3), and I almost didn't bother writing any code for this blog post (more on this later). But something got the better of me and I decided I wanted to write some code before wrapping up Prolog, so I decided to write a magic square generator. A 3x3 magic square is a grid of 9 numbers where each row, column and diagonal have the same sum. Here is the code.
/*
Generates 3x3 magic squares in prolog
http://en.wikipedia.org/wiki/Magic_square
*/
magic_square(Puzzle, Solution, Sum) :-
Puzzle = [S11, S12, S13,
S21, S22, S23,
S31, S32, S33],
fd_all_different(Puzzle),
fd_domain(Puzzle, 1, 9),
fd_labeling(Puzzle), /* This line is very important to actually seeing the answers*/
/* Rows */
R1 = [S11, S12, S13],
R2 = [S21, S22, S23],
R3 = [S31, S32, S33],
/* Columns */
C1 = [S11, S21, S31],
C2 = [S12, S22, S32],
C3 = [S13, S23, S33],
/* Diagonals */
Diag1 = [S11, S22, S33],
Diag2 = [S13, S22, S31],
sum_list(R1, Sum1),
sum_list(R2, Sum2),
sum_list(R3, Sum3),
sum_list(C1, Sum4),
sum_list(C2, Sum5),
sum_list(C3, Sum6),
sum_list(Diag1, Sum7),
sum_list(Diag2, Sum8),
Sum1 = Sum2,
Sum2 = Sum3,
Sum3 = Sum4,
Sum4 = Sum5,
Sum5 = Sum6,
Sum6 = Sum7,
Sum7 = Sum8,
Sum = Sum8,
Solution = Puzzle.
It is quite straightforward and introduces a few functions for constraint solving. The first step we take is to break the input list into the various elements so we can define some subgoals for individual parts of the input. fd_all_different and fd_domain are a couple of finite domain constraints. fd_all_different simply constrains the elements of the list to all be unique, fd_domain lets you specify an integer range that the elements of the list must belong to; here the range is 1-9. If you increase this number you get more magic squares generated (it also takes longer to solve). I'll discuss fd_labeling a little bit later.
The rest of the code is straightforward, we identify the rows and columns, put their sums into variables and then specify that the sums must be the same. Finally we unify the Puzzle variable to the Solution variable and one of the sums we computed to the Sum variable so we can see them in the output. If we call the function as follows
magic_square([_, _, _, _, _, _, _, _, _], Soln, Sum).
We get a series of magic squares (note, the squares are represented as lists, each row is 3 elements long).
Soln = [2,7,6,9,5,1,4,3,8]
Sum = 15 ? ;
Soln = [2,9,4,7,5,3,6,1,8]
Sum = 15 ? ;
;
Soln = [4,3,8,9,5,1,2,7,6]
Sum = 15 ? ;
Soln = [4,9,2,3,5,7,8,1,6]
Sum = 15 ? ;
Soln = [6,1,8,7,5,3,2,9,4]
Sum = 15 ? ;
Soln = [6,7,2,1,5,9,8,3,4]
Sum = 15 ?
So what was the fd_labeling i skipped over earlier? As it happens i was able to write this solution (minus that one line) in fairly short order (under 20mins), but without this line you get an exception. If we take the initial snippet
magic_square(Puzzle, Solution, Sum) :-
Puzzle = [S11, S12, S13,
S21, S22, S23,
S31, S32, S33],
fd_all_different(Puzzle),
fd_domain(Puzzle, 1, 9),
Solution = Puzzle.
The output from prolog will be
| ?- magic_square([_, _, _, _, _, _, _, _, _], Soln, Sum).
Soln = [_#2(1..9),_#21(1..9),_#52(1..9),_#83(1..9),_#114(1..9),_#14
What we get back indicates that Prolog is part of the way there, it knows that the various numbers in the list need to be in a certain range, in fact if you specify 8 of the 9 numbers that will be enough to constrain the last number completely (given the fd_all_different). It took me a while to understand what this output meant, but basically my understanding is that, while the two previous fd_* functions have specified the domain and applied a constraint, Prolog will not start enumerating what the possibilities are for those number at this point, thus functions like sum_list will throw an exception. fd_labeling tells Prolog to start assigning actual labels (values) to the constrained list, and thus we can start enumerating through the various permutations to find ones that satisfy our constraints.
Closing Thoughts on Prolog
I feel like I just scratched the surface of Prolog, the coverage in the book seems somewhat shallow, and this is partly because I am so unfamiliar with language like Prolog it is harder for me to fill in the gaps as with something like Io. I expected this to a degree as when I got the book I felt Prolog would be the 'most different' language from what I am familiar with. Nonetheless the purpose of the book is to give a taste of a number of languages and I do feel I got that. However I feel I am quite far away from being able to do something particularly useful, for example how to make the above code (or the Sudoku solvers in the book) more general (so that they can take magic squares of any size for example) isn't something I readily know how to do at the moment. So I am overall left with a feeling that there is a lot I can't do in Prolog and that I wouldn't know where to start. My experience with the documentation is that it can be quite terse and somewhat hard to decipher (see the documentation for fd_labeling, which i found to be one of the more readable ones).
Lastly I wanted to think about some things that Prolog might be good for that relate to the kinds of things I work on that may provide fertile ground for future experimentation. One area related to work in data visualization is that of automatic layout with constraints. One problem we often deal with is placing things so that they maintain appropriate relationships with one another and are constrained to the screen space you have (a simple example may be optimally putting labels on charts). I wonder how hard it would be to write space filling algorithms for things like treemaps or even something like Wordle in Prolog? These seem like the kind of problem Prolog would be well suited for.
Another area that's been at the edge of my radar is semantic web technologies like RDF. Prolog's ability for logical inference and method of knowledge representation make it look like a likely candidate for reasoning of knowledge stored in this manner.
In any case it was an interesting peek at Prolog and I am excited to look at the next language, Scala!
Code for today is up on github.