Re: The n-queens problem

Hi Christian,

>     i'am trying to understand the n-queens program below
>  
>     :- lib(ic).
> queens_lists(N, Board) :-
>  
>  length(Board, N),
>  Board :: 1..N,
>  ( fromto(Board, [Q1|Cols], Cols, []) do
>   ( foreach(Q2, Cols), param(Q1), count(Dist,1,_)
>      do Q2 #\= Q1, Q2 - Q1 #\= Dist, Q1 - Q2 #\= Dist
>     )),
>     labeling(Board). 
>    
>  
>     but i can't one thing:  why the output is only a list with four 
> numbers? Shouldn't be four pairs
>     indicating the line and column in the board for each queen?

We don't need pairs, just integers: we know that any solution has 
exactly 1 queen in each row and column. The decision variables are 
effectively for each column, in which row the queen is located (we could 
equivalently decide for each row, in column the queen is located). So 
for n=4 the solution

column:  1 2 3 4
         ---------
row 1   | | |Q| |
         ---------
row 2   |Q| | | |
         ---------
row 3   | | | |Q|
         ---------
row 4   | |Q| | |
         ---------

can be represented by adopting the convention that the list represents 
the position (row, column) of each queen on the board:

	[(1,3), (2,1), (3,4), (4,2)]

or by adopting the convention that the list represents the position 
(row) of a queen for each column in order:

	[2, 4, 1, 3]

or by adopting the convention that the list represents the position 
(column) of a queen for each row in order:

	[3, 1, 4, 2]

-- 
Andrew Eremin
Research Assistant                   Tel: +44 (0)20 7594 8299
IC-Parc, Imperial College London     Fax: +44 (0)20 7594 8432
London SW7 2AZ                       Email: a.eremin@icparc.ic.ac.uk