# Solving N-queens 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.

 Video:

## Prolog Solution

In the programming language Prolog, it is easy to describe solutions of this task using CLP(ℤ) 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([Q|Qs]) :- safe_queens(Qs, Q, 1), safe_queens(Qs). safe_queens([], _, _). safe_queens([Q|Qs], Q0, D0) :- Q0 #\= Q, abs(Q0 - Q) #\= D0, D1 #= D0 + 1, safe_queens(Qs, Q0, D1). ```

Full code: queens.pl

You can use Scryer Prolog to try it. Start it with:
```      \$ scryer-prolog queens.pl
```
You can then run queries like:
```      ?- N = 8, n_queens(N, Qs), labeling([ff], Qs).
N = 8, Qs = [1,5,8,6,3,7,2,4]
;  ...

?- N = 20, n_queens(N, Qs), labeling([ff], Qs).
N = 20, Qs = [1,3,5,14,17,4,16,7,12,18|...]
;  ...

```
The n-th 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 is an example shell command you can try:
```   \$ scryer-prolog -g 'show(20,[ff])' queens.pl | \
gs -dNOPROMPT -g680x680 -dGraphicsAlphaBits=2 -r144 -q
```
The arguments of the predicate show/2 are:
1. the number of queens
2. a list of labeling options.
As a side-effect, you see an animation of the constraint solving process.

Sample PostScript file, a self-contained 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:

Example with 100 queens:

Challenges: Find solutions for many queens. Find good labeling and allocation strategies. ...

Further reading: Neumerkel at al., Visualizing Solutions with Viewers.

More CLP(ℤ) examples: https://github.com/triska/clpz

More about Prolog: The Power of Prolog

Main page