/* NON-ATTACKING QUEENS.
   Peter Ross 24 Nov 81.

   This generates solutions to the problem of placing N queens on an NxN
   board so that none attacks any other. To use, call queens(N) and it
   will print out a board with queens represented by 'Q'.
   Note: no solutions for N=2,3.
         speed of solution drops rapidly as you increase N - N=8 may
         cause you a ten-minute wait!

   Meta-level ideas: represent a position of a queen as p(r,c) meaning
         a queen in row r, column c. Then a solution will be represented
         as N of these with no r occuring twice (queens can't be on the
         same row) and no c occuring twice (queens can't be on the same
         column). THEREFORE we can order the solution, say by taking the
         rows in descending order (i.e. from N to 1). The c's will just
         be some permutation of 1 to N. So, tasks are (taking, say, N=4):
           a) form the rows set [4,3,2,1]
           b) form a permutation of it, e.g. [3,1,4,2]
           c) construct a position from this, viz.
                 [p(4,3),p(3,1),p(2,4),p(1,2)]
           d) check that this is 'safe', i.e. no diagonal attacks
           e) print the answer nicely.
         In the program below, (a) is the job of 'numl'
                               (b) is the job of 'perm' 
                               (c) is the job of 'pair'
                               (d) is the job of 'safe'
                               (e) is the job of 'spitout'
         The tricky one is (b): the key idea is that if [U|V] is a
         permutation of [X|Y] then V is a permutation of the list got
         by deleting U from [X|Y].
         The form of 'spitout' is more elaborate than strictly necessary,
         one could just print out the p(r,c) terms. The version below
         prints out a nice chessboard, using dashes to separate rows
         and vertical bars to separate cells within each row.
*/

queens(N) :-
         numl(N,L1),
         perm(L1,L),
         pair(L1,L,Q),
         safe(Q),
         spitout(N,Q), nl.

numl(0,[]).
numl(N,[N|L]) :- N>0, !, N1 is N-1, numl(N1,L).

perm([],[]).
perm([X|Y],[U|V]) :- del(U,[X|Y],W), perm(W,V).
del(X,[X|Y],Y).
del(U,[X|Y],[X|V]) :- del(U,Y,V).

pair([],[],[]).
pair([X|Y],[U|V],[p(X,U)|W]) :- pair(Y,V,W).

safe([]).
safe([P|Q]) :- check(P,Q), safe(Q).
check(_,[]).
check(P,[Q|R]) :- nodiag(P,Q), check(P,R).
nodiag(p(X1,Y1),p(X2,Y2)) :-
         X1+Y2 =\= X2+Y1,
         X1+Y1 =\= X2+Y2.

spitout(N,[]) :- tab(4), writedashes(N), nl, !.
spitout(N,[p(_,Y)|Z]) :-
         tab(4), writedashes(N), nl,
         tab(4), spit(N,Y), nl,
         spitout(N,Z).
spit(0,_) :- write('|'), !.
spit(N,Y) :- N =\= Y, write('| '), N1 is N-1, spit(N1,Y).
spit(N,Y) :- N = Y, write('|Q'), N1 is N-1, spit(N1,Y).
writedashes(0) :- write('-'), !.
writedashes(N) :- write('--'), N1 is N-1, writedashes(N1).