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