Solving Nqueens with Prolog
The task is to place N queens on an N×N chessboard in such a
way that none of the queens is under attack.
Prolog Solution
In Prolog, it is easy to
describe solutions of this task,
using CLP(FD) constraints which
are commonly used
for combinatorial tasks:
n_queens(N, Qs) :
length(Qs, N),
Qs ins 1..N,
safe_queens(Qs).
safe_queens([]).
safe_queens([QQs]) :
safe_queens(Qs, Q, 1),
safe_queens(Qs).
safe_queens([], _, _).
safe_queens([QQs], Q0, D0) :
Q0 #\= Q,
abs(Q0  Q) #\= D0,
D1 #= D0 + 1,
safe_queens(Qs, Q0, D1).


Full code: queens.pl
You can use SWIProlog >
5.6.50 to try it. Start it with:
$ swipl queens.pl
You can then run queries like:
? N = 8, n_queens(N, Qs), labeling([ff], Qs).
Qs = [1, 5, 8, 6, 3, 7, 2, 4] .
? N = 20, n_queens(N, Qs), labeling([ff], Qs).
Qs = [1, 3, 5, 14, 17, 4, 16, 7, 12, 18, 15, 19, 6, 10, 20, 11, 8, 2, 13, 9] .
? N = 100, time((n_queens(N,Qs),labeling([ff],Qs))).
% 2,304,144 inferences, 0.553 CPU in 0.555 seconds (100% CPU, 4168963 Lips)
Qs = [1, 3, 5, 57, 59, 4, 64, 7, 58...] .
The nth integer in the list denotes the row of the queen
that is placed in column n.
Animation
If you have the PostScript viewer "gs" installed, you can view an
animation of the
constraint solving process.
Here are a few example queries that you can try:
? show(4, [], Qs).
? show(N, [], Qs).
? show(50, [ff], Qs).
The arguments of the predicate show/3 are:
 the number of queens
 a list of labeling options as described in the
CLP(FD) documentation
 a list of row numbers, one for
each column, such that the queens in these positions do not attack
each other.
As a sideeffect, you see an animation of the
constraint solving process.
Sample PostScript file, a selfcontained saved animation
for 50 queens (open it with "gv" or "gs" to view
it): queens50.ps
Sample animation (requires JavaScript), showing 80 queens with labeling strategy ff: queens80.
Here is a picture of a finished animation:
? show(8, [ff], Qs).
Qs = [1, 5, 8, 6, 3, 7, 2, 4] ;
Qs = [1, 6, 8, 3, 7, 4, 2, 5] ;
...
Qs = [3, 5, 2, 8, 1, 7, 4, 6] .
Example with 100 queens:
? show(100, [ff], Qs).
Qs = [1, 3, 5, 57, 59, 4, 64, 7, 58...] .
Challenges: Find solutions for many queens. Find good labeling and
allocation strategies. ...
Further reading:
Neumerkel
at
al., Visualizing
Solutions with Viewers.
More CLP(FD) examples: https://github.com/triska/clpfd
More about Prolog
Main page