Home > Uncategorized > Prolog

Prolog

One way to gain better skills in programming is to learn a new language. The pragmatic programmer recommends one new language every year and I guess that might be a good goal. Readers of Seven languages in seven weeks might learn even more, though it should be kept in mind that quantity and quality is not the same thing, I guess. The author expresses the idea of learning a new language (programming or spoken) using the following inspirational words:

A second language can help you encounter new worlds. You may even seek enlightenment, knowing every new language can shape the way you think.

The author covers Ruby, Io, Prolog, Scala, Erlang, Clojure and Haskell. One that has also been on my todo list is Prolog. Prolog belongs to the domain of logic programming and thus differs quite a bit from what I am used to, which of course contributes to my curiousness. I downloaded SWI-Prolog which was said to be mature and maybe more importantly, free. I decided to try to write a Sudoku solver, guessing that Prolog might be able to solve this with elegance, but also since it was also a problem I was being familiar with, having written solvers in both F#, C# and Powershell before. My task was prematurely aborted though when I searched for help about how to implement a matrix transpose method. The first hit when googling for “prolog tranpose” lead to a library called clpfd (Constraint Logic Programming over Finite Domains) which defined the function I was trying to express. However, as a sample usage of this function, the documentation also provided a – that’s right – a sudoku solver.

:- use_module(library(clpfd)).

sudoku(Rows) :-
        length(Rows, 9), maplist(length_(9), Rows),
        append(Rows, Vs), Vs ins 1..9,
        maplist(all_distinct, Rows),
        transpose(Rows, Columns), maplist(all_distinct, Columns),
        Rows = [A,B,C,D,E,F,G,H,I],
        blocks(A, B, C), blocks(D, E, F), blocks(G, H, I).

length_(L, Ls) :- length(Ls, L).

blocks([], [], []).
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-
        all_distinct([A,B,C,D,E,F,G,H,I]),
        blocks(Bs1, Bs2, Bs3).

Magnificent! A kind soul at stackoverflow had also published an explanation for prolog dummies (like myself). One important row was not explained though which had been pointed out but not corrected. The row not explained was

“append(Rows, Vs), Vs ins 1..9”

With a bit of trouble I was able to figure it out myself;

  • append(Rows, Vs) is predefined and takes a list of lists and returns the concatenation. For example append([[1,2],[3],[4,5]],X) yields X=[1,2,3,4,5].
  • Vs ins 1..9 means that every element in Vs should be constrained to values in the interval 1 to 9. Ins is defined I clpfd.

Nice, but I still wanted to write something myself. So… here is my n-queen solver instead:

:- use_module(library(clpfd)).

% usage: solution([X1,X2,X3,X4,X5,X6,X7,X8]).
solution(X) :-
    length(X, Size),
    X ins 1..Size,
    all_distinct(X),
    diagonal(X),
    label(X).

diagonal([]).
diagonal([X|XS]) :- diagonal(X, XS, 0), diagonal(XS).

diagonal(_, [], _).
diagonal(X, [Y|YS], I) :-
    J is I+1,
    X #\= Y + J,
    X #\= Y – J,
    diagonal(X, YS, J).

I close this session by giving a reference to a prolog tutorial that I liked:

http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/contents.html

(You might enjoy reading section 2.11 provides another n-queen solver and compare it to mine. The example uses a clever encoding to avoids checks for queens on the same row.)

Advertisements
Categories: Uncategorized
  1. mat
    July 26, 2011 at 10:39 pm

    Very nice. In your N-queens solution, if you replace label(X) by labeling([ff], X) for first-fail labeling, you can quickly get solutions also for larger board sizes. Try for example ?- length(Ls, 100), solution(Ls). with both strategies.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: