5.1 Example: Queens

Model

We will use a clever model avoiding possible symmetries and minimizing the number of propagators.

We assume that the queens are numbered from 1 to , and that the -th queen is always placed in the -th column. For every queen we have one variable R_i saying in which row the queen is placed. The model guarantees by construction that two queens are never placed in the same column. To ensure that two queens are never in the same row, we impose the constraint that the variables $R_1,\ldots,R_N$ are pairwise distinct.

To enforce that two queens are never in the same diagonal, we need to impose the constraints

$R_i+(j-i)\neq R_j \qquad \hbox{and} \qquad R_i-(j-i)\neq R_j$

for all , such that $1\le i<j\le N$ . Equivalently, we can impose the constraints

$R_i-i\neq R_j-j \qquad \hbox{and} \qquad R_i+i\neq R_j+j$

for all , such that $1\le i<j\le N$ . This is equivalent to saying that the sequences

$R_1-1\;,\ldots,\;R_N-N \qquad \hbox{and} \qquad R_1+1\;,\ldots,\;R_N+N$

are both nonrepetitive. Since Oz has a special propagator for the constraint stating the nonrepetitiveness of such sequences, this formulation requires only two propagators, one for each sequence.

Distribution Strategy

We distribute on the variables $R_1,\ldots,R_N$ using a first-fail strategy that tries the value in the middle of the domain of the selected variable first. This strategy works well even for large N.

fun {Queens N}
   proc {$ Row}
      L1N ={MakeTuple c N}  
      LM1N={MakeTuple c N}
   in 
      {FD.tuple queens N 1#N Row}
      {For 1 N 1 proc {$ I}
                    L1N.I=I LM1N.I=~I
                 end}
      {FD.distinct Row}
      {FD.distinctOffset Row LM1N}
      {FD.distinctOffset Row L1N}
      {FD.distribute generic(value:mid) Row}
   end 
end

Figure 5.2: A script for the N-queens Problem.

Script

Figure 5.2 shows a parameterized script for the N-Queens Problem. The actual script is created by the procedure Queens, which takes N as parameter. The script constrains its root variable Row to a tuple having a component for every queen. This implicitly creates the variables $R_1,\ldots,R_N$ of the model.

The statements

{FD.distinct Row} {FD.distinctOffset Row LM1N} {FD.distinctOffset Row L1N}

create propagators for the constraints stating that the sequences

`Row.1`	...	`Row.N`
`Row.1-1`	...	`Row.N-N`
`Row.1+1`	...	`Row.N+N`

be non repetitive.