Did you know ... | Search Documentation: |

Example: Eight queens puzzle |

- HOME
- DOWNLOAD
- DOCUMENTATION
- TUTORIALS
- Beginner▶
- Advanced▶
- Web applications▶
- Semantic web▶
- Graphics▶
- Machine learning▶
- External collections▶
- For packagers▶

- COMMUNITY
- COMMERCIAL
- WIKI

- Documentation
- Reference manual
- The SWI-Prolog library
- library(clpfd): CLP(FD): Constraint Logic Programming over Finite Domains
- Introduction
- Arithmetic constraints
- Declarative integer arithmetic
- Example: Factorial relation
- Combinatorial constraints
- Domains
- Example: Sudoku
- Residual goals
- Core relations and search
- Example: Eight queens puzzle
- Optimisation
- Reification
- Enabling monotonic CLP(FD)
- Custom constraints
- Applications
- Acknowledgments
- CLP(FD) predicate index
- Closing and opening words about CLP(FD)

- library(clpfd): CLP(FD): Constraint Logic Programming over Finite Domains

- The SWI-Prolog library
- Packages

- Reference manual

We illustrate the concepts of the preceding sections by means of the
so-called *eight queens puzzle*. The task is to place 8 queens on
an 8x8 chessboard such that none of the queens is under attack. This
means that no two queens share the same row, column or diagonal.

To express this puzzle via CLP(FD) constraints, we must first pick a
suitable representation. Since CLP(FD) constraints reason over
*integers*, we must find a way to map the positions of queens to
integers. Several such mappings are conceivable, and it is not
immediately obvious which we should use. On top of that, different
constraints can be used to express the desired relations. For such
reasons, *modeling* combinatorial problems via CLP(FD) constraints
often necessitates some creativity and has been described as more of an
art than a science.

In our concrete case, we observe that there must be exactly one queen
per column. The following representation therefore suggests itself: We
are looking for 8 integers, one for each column, where each integer
denotes the *row* of the queen that is placed in the respective
column, and which are subject to certain constraints.

In fact, let us now generalize the task to the so-called *N queens
puzzle*, which is obtained by replacing 8 by *N* everywhere it
occurs in the above description. We implement the above considerations
in the
**core relation** n_queens/2, where the
first argument is the number of queens (which is identical to the number
of rows and columns of the generalized chessboard), and the second
argument is a list of *N* integers that represents a solution in
the form described above.

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).

Note that all these predicates can be used in *all directions*:
We can use them to *find* solutions, *test* solutions and *complete*
partially instantiated solutions.

The original task can be readily solved with the following query:

?- n_queens(8, Qs), label(Qs). Qs = [1, 5, 8, 6, 3, 7, 2, 4] .

Using suitable labeling strategies, we can easily find solutions with 80 queens and more:

?- n_queens(80, Qs), labeling([ff], Qs). Qs = [1, 3, 5, 44, 42, 4, 50, 7, 68|...] . ?- time((n_queens(90, Qs), labeling([ff], Qs))). % 5,904,401 inferences, 0.722 CPU in 0.737 seconds (98% CPU) Qs = [1, 3, 5, 50, 42, 4, 49, 7, 59|...] .

Experimenting with different search strategies is easy because we have separated the core relation from the actual search.

Tags are associated to your profile if you are logged in

Tags: