The N Queens Problem using Simulated Annealing

This code requires the Simulated Annealing package.

 * queens(N) attempts to solve the N queens problem.

/* perturb(Xs, Ys) is true if the list Xs is a permutation of the integers */
/*   0 to Size-1, and Ys is the same as Xs except that two pseudo-randomly */
/*   selected elements have been exchanged.                                */
perturb(Xs, Ys):-
  random(Size, I),
    random(Size, J),
  I =\= J, !,
  subst(Xs, I, -1, Xs1),
  subst(Xs1, J, I, Xs2),
  subst(Xs2, -1, J, Ys).

/* subst(Ls, X, Y, Ms) is true if the list Ms is the same as the list Ls   */
/*   except that the first occurrence of the element X is replaced by Y.   */
subst([X|Ls], X, Y, Ms):-!, Ms=[Y|Ls].
subst([L|Ls], X, Y, [L|Ms]):-subst(Ls, X, Y, Ms).

energy(Rows, Energy):-
  energy_1(Rows, 0, Pluses, Minuses),
  energy_2(Pluses, 0, Energy0),
  energy_2(Minuses, Energy0, Energy).

energy_1([], _, [], []).
energy_1([Row|Rows], Column, [Plus|Pluses], [Minus|Minuses]):-
  Plus is Column + Row,
  Minus is Column - Row,
  Column1 is Column + 1,
  energy_1(Rows, Column1, Pluses, Minuses).

energy_2([], Energy, Energy).
energy_2([X|Xs], Energy0, Energy):-
  member(X, Xs), !,
  /* Penalize a queen which is on the same diagonal as another queen */
  Energy1 is Energy0 + 1,
  energy_2(Xs, Energy1, Energy).
energy_2([_|Xs], Energy0, Energy):-
  energy_2(Xs, Energy0, Energy).

output(optimal, Rows, 0):-
  /* Solution found */
  size(Size), !,
  output_1(Size, Size, Rows).
output(iterations, _, _):-
  write('Solution not found - all iterations performed'), nl.
output(nochanges, _, _):-
  write('Solution not found - no changes made at a given temperature'), nl.

output_1(0, _, _):-!.
output_1(N, Size, Rows):-
  N1 is N - 1,
  nth(Rows, Before, N1), !,
  After is Size - Before - 1,
  empty(Before), write('Q'), empty(After), nl,
  output_1(N1, Size, Rows).
empty(N):-write('+'), N1 is N - 1, empty(N1).  

/* nth(+Xs, ?N, ?X) is true if X is the N-th (base 0) element of the       */
/*   list Xs.                                                              */
nth(Xs, N, X):-nth_1(Xs, X, 0, N).

nth_1([X|_], X, N, N).
nth_1([_|Xs], X, N0, N):-
  N1 is N0 + 1,
  nth_1(Xs, X, N1, N).

LPA Index     Home Page