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.

/* 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  is Row + Col, \+ member(RowPlusCol,  B),
  /* All squares on the same SW-NE diagonal have the same value of Row-Col */
  RowMinusCol is Row - Col, \+ member(RowMinusCol, C),
  Col1 is 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 is I + 1, integers(I1, N, Is).

LPA Index     Home Page

Valid HTML 4.01 Strict