/* 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).