/*      $Id: queens.prl,v 1.2 2009/08/31 15:39:01 mtrillo Exp $    */

/*
   N-queens problem.

   Written by Marco Trillo on January 9, 2009.

   Serves as a testcase and sample for SILXPI.
 */

mapsucc([],[]).
mapsucc([H | T], [succ(H) | Mapt]) :- mapsucc(T, Mapt).
mapprev([],[]).
mapprev([succ(H) | T], [H | Mapt]) :- mapprev(T, Mapt).
mapprev([zero | T], Mapt) :- mapprev(T, Mapt).
noteq(X, X) :- !, fail.
noteq(X, Y).
notin(X, []).
notin(X, [Y | T]) :- noteq(X,Y), notin(X, T).
takeout(X, [X | Z], Z).
takeout(X, [R | Z], [R | S]) :- takeout(X, Z, S).

queens([], X, Y, R, I, R).
queens(Lpos, Llist, Rlist, R, I, Result) :- 
        takeout(Pos, Lpos, Lnew),
        notin(Pos, Llist),
        notin(Pos, Rlist),
        mapprev([Pos | Llist], Lmap),
        mapsucc([Pos | Rlist], Rmap),
        queens(Lnew, Lmap, Rmap, [[Pos | I] | R], succ(I), Result)
.

enumlist-r(zero, Acc, Acc).
enumlist-r(succ(X), Acc, Result) :- enumlist-r(X, [succ(X) | Acc], Result).

queens(X, L) :- enumlist-r(X, [], Lpos), 
                queens(Lpos, [], [], [], succ(zero), L).