/*
 * range(Anfang, Ende, Liste)
 *    Liste enthaelt die ganzen Zahlen von Anfang bis Ende.
 */
range(First, Last, List):-
    bagof(X, between(First, Last, X), List).

/*
 * select_first(Erstes, Liste, Rest)
 *     Erstes ist das erste Element von Liste,
 *     Rest ist die Restliste (ohne Erstes).
 */
select_first(First, [First| Rest], Rest).

/*
 * safe(Damen)
 *     Alle Damen stehen sicher.
 */
safe([]).
safe(Queens):-
    select_first(Queen, Queens, Rest_Queens),
    safe(Rest_Queens),
    \+ attack(Queen, Rest_Queens).

/*
 * attack(Queen, Queens)
 *     Die Queen und (mindestens) eine der Queens
 *     bedrohen sich gegenseitig.
 */
attack(Queen, Queens):- attack(Queen, 1, Queens).

/*
 * attack(Queen, Queens)
 *     Die Queen und eine der Queens, die alle
 *     mindestens N Reihen entfernt sind, bedrohen sich
 *     gegenseitig.
 */
attack(Queen, N, [First| _]):-
    Queen is First + N.
attack(Queen, N, [First| _]):-
    Queen is First - N.
attack(Queen, N, [_| Rest]):-
    N1 is N + 1,
    attack(Queen, N1, Rest).

/*
 * queensP(N, Queens)
 *     Qs ist eine Loesung des N-Damen-Problems.
 *     (formuliert mit Permutation)
 */
queensP(N, Queenss):-
    range(1, N, Ns),
    permutation(Ns, Queenss),
    safe(Queenss).

/*
 * queens(N, Queens)
 *     Queens ist eine Loesung des N-Damen-Problems.
 */
queens(N, Queens):-
    range(1, N, Ns),
    queens(Ns, [], Queens).

/*
 * quuens(UnplacedQueens, SafeQueens, Queens)
 *     Queens ist eine Loesung des N-Damen Problems.
 *     Die Liste Queens enthaelt die noch nicht plazierten Damen,
 *     SafeQueens enthaelt die bereits sicher plazierten Damen.
 */
queens(UnplacedQueens, SafeQueens, Queens):-
    select(Queen, UnplacedQueens, RestQueens),
    \+ attack(Queen, SafeQueens),
    queens(RestQueens, [Queen| SafeQueens], Queens).
queens([], Queens, Queens).