A programming language is like a tool. Every tool has a specific purpose. One tool does one job better and another tool does another job better. Programming Languages should be thought of the same way.

Why Constraint Programming

The N-Queens puzzle is very popular and we were able to find several working examples in C and in Prolog.  We analyzed, compiled and tested all these programs and weighed all the pros and cons these two types of languages.

Prolog, being a higher level language, is intuitively easier to understand and easier to program. You can think about the problem with more abstraction. The challenge in actually programming in prolog is that you need to be able to correctly “define” and thus “constrain” the program to do what needs to be done. You don’t have to worry about data types, pointers, data structures and other lower level issues. All the prolog solutions we came across were between 40 and 50 lines of code. On the downside, it was inconvenient when trying to test any n size greater than 12. Trying to solve the puzzle for n=13 takes about 148 seconds.

We found one good example of the n queens problem written in C. We compiled it under Visual Studio 2008, and ran it. The obvious upside in the C program was the speed. It could still solve the puzzle in under a second for n=13. That’s a huge difference compared with the prolog program.  The downside is trying to understand the code and trying to write the code. It’s not as obvious to see what’s happening. The level of abstraction is not as narrow as it is in prolog. On top having to worry about correctly implementing a solution, you have to worry about correctly defining a data structure, defining the correct data types, properly handling arrays and pointers, and other lower level issues not in any way related to the puzzle’s algorithm. The C program that we were testing was 400 lines of code. 236 lines if you remove the comments. That’s almost 5 times the size of the prolog program.

Time Comparisons between Prolog and C

Next, we wanted to discuss the simplicity in solving the n-queens problem in prolog. Let’s define our solution for N=4.

We define our solution by stating that each of the 4 queens must occupy it’s very own row, column, downward diagonal, and upward diagonal on a 4×4 board.

And that’s our definition! Now we need to tell prolog to do this and write our constraints.

%% DEFINE OUR BOARD     
%% sq(y-coord, x-coord, downward-diag, upward-diag) 
 sq(1,1,4,1).
 sq(1,2,5,2).
 sq(1,3,6,3).
 sq(1,4,7,4).
 sq(2,1,3,2).
 sq(2,2,4,3).
 sq(2,3,5,4).
 sq(2,4,6,5).
 sq(3,1,2,3).
 sq(3,2,3,4).
 sq(3,3,4,5).
 sq(3,4,5,6).
 sq(4,1,1,4).
 sq(4,2,2,5).
 sq(4,3,3,6).
 sq(4,4,4,7).
 
%% CONSTRAINT
%% We define our solution by stating that
%% each of the 4 queens must occupy it’s
%% very own row, column, downward diagonal,
%% and upward diagonal on a 4x4 board.
 chess(A,B, E,F, I,J, M,N) :-
 sq(A,B,C,D), sq(E,F,G,H), sq(I,J,K,L), sq(M,N,O,P),
 A=1, E=2, I=3, M=4,
 A\=E, A\=I, A\=M,
 B\=F, B\=J, B\=N,
 C\=G, C\=K, C\=O,
 D\=H, D\=L, D\=P,
 E\=I, E\=M,
 F\=J, F\=N,
 G\=K, G\=O,
 H\=L, H\=P,
 I\=M,
 J\=N,
 K\=O,
 L\=P.

Here is our output once we run our program:

?- chess(A,B,E,F,I,J,M,N).
 
A = 1,
B = 2,
E = 2,
F = 4,
I = 3,
J = 1,
M = 4,
N = 3 ;

Which means:  { Q1(1, 2) , Q2(2, 4) , Q3(3, 1) , Q4(4, 3) }

Which is of course, the right solution. Here was the other solution.

A = 1,
B = 3,
E = 2,
F = 1,
I = 3,
J = 4,
M = 4,
N = 2 ;

Which means:  { Q1(1, 3) , Q2(2, 1) , Q3(3, 4) , Q4(4, 2) }