; This program solves the n-queens problem how to place N chess queens
; on a N x N chess board in such a way that no queen attacks any other
; It is taken (with some minor modifications) from Sterling & Shapiro 14.1
; the top-level query is e.g ? n_queens (8, Solution).
; solutions are represented by lists of integers, [1,2,3,....] represents
; the non-solution a1, b2, c3, .... (in European chess notation)

? seeing(ThisProgram), assert([anew, new(ThisProgram)]).

n_queens (N,Qs)  <- 
     range (1, N, Ns), 
     queens (Ns, [], Qs).

queens (UnplacedQs, SafeQs, Qs) <-
     select (Q, UnplacedQs, UnplacedQs'),
     safe (Q, SafeQs),
     queens (UnplacedQs', [Q|SafeQs], Qs).
queens ([], Qs, Qs).

safe (Q, SafeQs)  <- noattack (Q, 1, SafeQs).


noattack (X, N, []).
noattack (X, N, [Y|Ys]) <-
     X =\= Y + N,
     X =\= Y - N,
     noattack (X, N+1, Ys).

select (X, [X|Xs], Xs).
select (X, [Y|Ys], [Y|Zs]) <-  select (X, Ys, Zs).

range (From, To , [From|Rest]) <-  
     From < To,
     From' := From + 1,
     range (From', To, Rest).
range (N, N, [N]).

; The rest of this program is not essential, I used it for benchmarking
; (the 8-queen problem takes 440 secs on my QL)

benchmark (G) <-
     time (T), 
     do (G), 
     time (T'), 
     N := T' - T,
     nl, writeln([G, "takes ", N, " seconds"]), !. 

do (G) <- do_until_it_fails (G).
do (G).

do_until_it_fails (G) <-   G, writeln([G]), fail.

;*********************     DISPLAYING A BOARD ***************************

display_board ([Q|Qs], Size) <- 
     display_row (Q, Size), 
     display_board (Qs, Size).
display_board ([], _) <- ink (7), !.


display_row ( _, 0)   <-  !, nl. 
display_row (Q, Q)    <-  
     !, 
     ink (7),write (" Q "), ink (2),
     S := Q-1, display_row (Q,S).
display_row (Q, Size) <-  
     !, 
     write (" . "), 
     S := Size - 1, display_row (Q, S). 

demo (N) <- 
     cls, 
     n_queens(N,Qs), 
     at(0,0), ink (2), display_board (Qs,N), ink (7),writeln([Qs]),
    fail.