CS314: More notes on nQueens program
December 6, 2002

1. next Tuesday I will explain why the number of distinct placements
of 4 queens on a 4 by 4 chessboard is 16 choose 4 ( 16 ).
                                                  (  4 )

2. the length() function in nQueens is a built-in function for
Prolog. It is invertible as a predicate so it can be called with either 
(or both) of its parameters as an unbound variable.

**************
83 romulus!programs> prolog 
SICStus 3.7: Tue Sep 08 19:55:50 MET DST 1998 
Licensed to cs.rutgers.edu 
| ?- [nqueens]. 
{consulting /ug/u3/ryder/314/prolog/programs/nqueens.pl...} 
{/ug/u3/ryder/314/prolog/programs/nqueens.pl consulted, 10 msec 
yes
| ?- length(P,2).         ;generates list of length 2
P = [_A,_B] ? ;  
no 
| ?- length([w,d,e],X).   ;generates length of given list 
X = 3 ? ;  
no 
| ?- length(X,Y).         ;generates lists of lengths 1, 2,3,... lazily
X = [], 
Y = 0 ? ;  

X = [_A], 
Y = 1 ? ;  

X = [_A,_B], 
Y = 2 ? ;  

X = [_A,_B,_C], 
Y = 3 ? ;  

X = [_A,_B,_C,_D], 
Y = 4 ? ;  

X = [_A,_B,_C,_D,_E], 
Y = 5 ? 

yes
**********

3. in the nQueens program, the key rule is for queens().

queens(P) :- queen_no(N), length(P,N), placement(P), ok_place(P).

here we use length(P,N) where P is an unbound variable,
and parameter N is set by the previous subgoal queen_no(N) which unifies
with fact queen_no(4).

so now let's consider placement() and how it works. 

the rules for placement show that it builds lists of Prolog tuples (pairs)
where each pair describes a board position (e.g., (1,2)). you can run
queries with placement(P) where P is unbound to see the answers it generates 
and the generation order. Clearly we see that the search tree corresponding
to placement(P) where P is unbound, contains an unbounded path.

***************************
| ?- placement(P).

P = [] ? ;

P = [(1,1)] ? ;

P = [(1,1),(1,1)] ? ;

P = [(1,1),(1,1),(1,1)] ? ;

P = [(1,1),(1,1),(1,1),(1,1)] ? ;

P = [(1,1),(1,1),(1,1),(1,1),(1,1)] ? ;

P = [(1,1),(1,1),(1,1),(1,1),(1,1),(1,1)] ? ;

P = [(1,1),(1,1),(1,1),(1,1),(1,1),(1,1),(1,1)] ? ;

P = [(1,1),(1,1),(1,1),(1,1),(1,1),(1,1),(1,1),(1,1)] ? 

yes
******************************

These answers do not look like very good candidate queen placements
because we need to run through all lists of arbitrary length
containing only the board position (1,1) before trying to add any
other board positions!  (this is what happens when a search tree
contains an unbounded path; computation 'gets stuck' on exploring that
path and never reaches the rest of the tree!) 

However, when we run placement(P) after subgoal length(P,N) with N
bound to 4, the values returned by the predicate are different.

***************

| ?- length(P,4),placement(P).  
P = [(1,1),(1,1),(1,1),(1,1)] ? ;  
P = [(1,1),(1,1),(1,1),(1,2)] ? ;  
P = [(1,1),(1,1),(1,1),(1,3)] ? ;  
P = [(1,1),(1,1),(1,1),(1,4)] ? ;  
P = [(1,1),(1,1),(1,1),(2,1)] ? ;  
P = [(1,1),(1,1),(1,1),(2,2)] ? ;  
P = [(1,1),(1,1),(1,1),(2,3)] ? ;
P = [(1,1),(1,1),(1,1),(2,4)] ? 

yes
*******************

Thus, placement generates all the lists of length 4, which contain 4 pairs of 
board positions. Clearly, when the first answer returned by placement is 
checked by ok_place(), it will be rejected and the backtracking model
of computation will demand that placement generate another answer (computation
proceeds as if we typed ";" after obtaining the answer to a query).
Many of these answers will have to be checked before a list with no duplicate
elements is obtained.  And then many such lists will need to be checked
before a legal placement for the queens is found. 

Clearly this unoptimized version of the program is analogous to our
'naive' coloring algorithm for the countries.

4. Debugging in prolog If you turn on the trace, and then reply with
"?" to the prompt, the system will show you all the possible debugging
commands you can use, including looking for ancestor subgoals, skipping 
to the next call of a particular predicate, planting breakpoints etc.