# Re: The n-queens problem

From: Andrew Eremin <a.eremin_at_icparc.ic.ac.uk>
Date: Wed 11 Aug 2004 01:58:53 PM GMT
Message-ID: <411A261D.5040607@icparc.ic.ac.uk>
```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
```
Received on Wed Aug 11 15:02:32 2004

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:29 PM GMT GMT