Next: LLP COMPILER SYSTEM Up: EXAMPLES Previous: Cryptarithmetic Puzzles

## N-Queens

The last example is the N-queens problem. The following program maps each column, each right-up diagonal, and each right-down diagonal to resources c(_), u(_), and d(_) respectively. Attack check is done automatically by consuming c(j), u(i+j), and d(i-j) when placing a queen at (i,j).

```queen(N, Q) :- (n(N), result(Q)) -<> place(N).

place(1) :-
(c(1),u(2),d(0)) -<> (n(N), solve(N, [])).
place(I) :-
I > 1, I1 is I-1,
U1 is 2*I, U2 is 2*I-1, D1 is I-1, D2 is 1-I,
(c(I),u(U1),u(U2),d(D1),d(D2)) -<> place(I1).

solve(0, Q) :-
result(Q), top.
solve(I, Q) :-
I > 0, c(J), U is I+J, u(U), D is I-J, d(D),
I1 is I-1, solve(I1, [J|Q]).
```

For example, at the execution of the goal queen(8,Q), the place predicate adds the resources c(1), ..., c(8), u(2), ..., u(16), d(-7), ..., d(7), then solve(8,[]) is called. The solve predicate finds a solution by consuming c(j), u(i+j), and d(i-j) for each row i=1..8. After placing 8 queens, the result is returned through the slot result(Q), and remaining resources are erased by the top predicate.

Naoyuki Tamura
Thu May 8 20:39:01 JST 1997