Sunday, November 2, 2008

Constraint programming

I've exercises the programming part brain by solving problems at ProjectEuler.net now and then. Has some fun problems which usually don't take too much time to solve (I haven't gotten to the difficult ones yet...). Today I finally got to exercise my knowledge of constraint-programming in Prolog. My master's thesis was about implementing multithreading in Prolog, and my supervisor is a die-hard constraint programmer, so he would never forgive me if I solved the problem by brute force. :-)

The problem in question is Problem 9: find the only Pythagorean triplet {X,Y,Z} such that X + Y + Z = 1000. Here's the constraint solution:

triplet([X, Y, Z]) :-
X #\= 0, Y #\= 0, Z #\= 0,
X**2 + Y**2 #= Z**2,
X + Y + Z #= 1000,
fd_labeling([X, Y, Z]).

It isn't the shortest solution, but it has a clearness to it which is just amazing. It almost feels like cheating. (If you want to try it, you can use GNU Prolog).

No comments: