next up previous
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