Logic Problems in Prolog

Lately, I've been very into the idea of using prolog to solve logical problems/puzzles. In my opinion, prolog is a fantastic tool to simply brute force a solution with very elegant and short code. This is largely because of prolog's automatic backtracking/retrying features. Running time can be fairly bad, but the efficiency with which you can manufacture solutions is a big plus. Here is a very nice explanation of the awesomeness of prolog ^.^

Googling 'classic logic puzzles' lead me here. There were a lot of good puzzles of varying difficulty on this site. Some that I couldn't program I just sat and thought out. It was very enjoyable ^.^

Here is a problem that I was able to write a program for. The problem is simple, but the prolog code is also quite nice and easy to read.

Problem

What is the four-digit number in which the first digit is one-third the second, the third is the sum of the first and second, and the last is three times the second?

Code

digit(1). digit(2). digit(3). digit(4). digit(5).
digit(6). digit(7). digit(8). digit(9). digit(0).

not(X) :- X, !, fail.
not(_) .

fourdigitnum :-
digit(A), digit(B), digit(C), digit(D), not(A = 0),
First is B // 3, Third is A + B, Last is 3 * B,
A = First, C = Third, D = Last,
write(A), write(B), write(C), write(D).

Explanation

The program just grabs four digits(number ABCD), and ensures that A isn't zero (0999 isn't a true four digit number). It new variables First, Third, Last and assigns to them the values that should be equal to the corresponding digits (A, C, and D). Finally prolog tries to pairwise unify the digits A, C, and D with their respective variables First, Third, and Last(unification of two variables succeeds if and only if the two variables have the same value). Unification succeeding implies that the number ABCD meets the requirements of the puzzle; so prolog writes the number and leaves the function.

Here is the output of the function

Diesel$ gprolog
GNU Prolog 1.3.1
By Daniel Diaz
Copyright (C) 1999-2009 Daniel Diaz
| ?- [fourdigit].
compiling /Users/Diesel/Archive/code/prolog/fourdigit/fourdigit.pl for byte code...
/Users/Diesel/Archive/code/prolog/fourdigit/fourdigit.pl compiled, 25 lines read - 2419 bytes written, 17 ms

(1 ms) yes
| ?- fourdigitnum.
1349

true ?

As you can see (and if you hadn't already figured it out), the number in question is 1349. The last line 'true?' allows you to tell the function to try another number or try all possible numbers. It turns out that 1349 is the only number that works (0000 would work if A could be zero), and this can be figured out with just pencil and paper or even in the heads of some bright folks =) either way I enjoyed writing this code because it is a small, quickly written example of prolog's brute forcing power!

Check back for more puzzles and prolog solutions soon.