#### The N Queens Problem

You have to place N queens on an N-by-N chessboard so that no two queens
are on the same row, column or diagonal.

check_determ
domains
int = integer
ints = int*
predicates
nondeterm remove(int,ints,ints)
nonmember(int,ints)
integers(int,int,ints)
nondeterm queens(int,ints)
nondeterm queens_1(ints,int,ints,ints,ints,ints)
clauses
/* queens(N, Queens) is true if Queens is a placement that solves the N */
/* queens problem, represented as a permutation of the list of integers */
/* [1, 2, ..., N]. */
queens(N, Queens):-
N > 0,
integers(1, N, Rows),
queens_1(Rows, N, [], [], [], Queens).
queens_1([], 0, Queens, _, _, Queens).
queens_1(Rows, Col, A, B, C, Queens):-
remove(Row, Rows, Rows1),
/* All squares on the same NW-SE diagonal have the same value of Row+Col */
RowPlusCol = Row + Col, nonmember(RowPlusCol, B),
/* All squares on the same SW-NE diagonal have the same value of Row-Col */
RowMinusCol = Row - Col, nonmember(RowMinusCol, C),
Col1 = Col - 1,
queens_1(Rows1, Col1, [Row|A], [RowPlusCol|B], [RowMinusCol|C], Queens).
/* integers(M, N, Is) is true if Is is the list of integers from M to N */
/* inclusive. */
integers(N, N, [N]):-!.
integers(I, N, [I|Is]):-I < N, I1 = I + 1, integers(I1, N, Is).
/* remove(X, Ys, Zs) is true if Zs is the result of removing one */
/* occurrence of the element X from the list Ys. */
remove(X, [X|Ys], Ys).
remove(X, [Y|Ys], [Y|Zs]):-remove(X, Ys, Zs).
/* nonmember(X, Xs) is true if X is not a member of the list Xs. */
nonmember(X, [Y|Ys]):-X <> Y, nonmember(X, Ys).
nonmember(_, []).

Turbo Prolog Index
Home Page