3.7.163. n-Amazons

modelling: n-Amazons A constraint that can be used for modelling the n-Amazons problem. Place n Amazons on an n by n chessboard in such a way that no Amazon attacks another. We say that two columns (respectively two rows) of a chessboard are almost adjacent if and only if the two columns (respectively the two rows) are separated by a single column (respectively a single row). Two Amazons attack each other if at least one of the following conditions holds:

  1. They are located on the same column, on the same row or on the same diagonal.

  2. They are located either on adjacent columns and on almost adjacent rows, or on almost adjacent columns and on adjacent rows.

As shown by these conditions, an Amazon combines the movements of a queen and of a knight. FigureΒ 3.7.43 illustrates the movements of an Amazon. The n-Amazons problem has no solution when n is smaller than 10.

Figure 3.7.43. Illustration of the moves of an Amazon: moves labelled by 1 correspond to queen's moves, while moves labelled by 2 correspond to knight's moves

We now show how to model the n-Amazons problem with six global constraints. We start from the model that is used for the n-queens problem. We associate to the i th column of the chessboard a domain variable X i that gives the row number where the corresponding queen is located.

If we combine the constraints of the form |X i -X i+1 |β‰ 2 (1≀i≀n-1) with the three πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints we get the conjunction of constraints X i -X i+1 β‰ 0 ∧ |X i -X i+1 |β‰ 1 ∧ |X i -X i+1 |β‰ 2 (1≀i≀n-1). This conjunction of three disequalities can be expressed as a single inequality of the form |X i -X i+1 |>2 (1≀i≀n-1). Furthermore all these inequalities can be combined into a single πšœπš–πš˜πš˜πšπš‘ constraint of the form πšœπš–πš˜πš˜πšπš‘(n-1,2,〈X 1 ,X 2 ,β‹―,X n βŒͺ).Since we enforce for all pairs of consecutive variables X i , X i+1 (1≀i≀n-1) the constraint |X i -X i+1 |>2, the name πšœπš–πš˜πš˜πšπš‘ seems odd. However the name πšœπš–πš˜πš˜πšπš‘ stands from the situation where the number of inequalities constraints should be minimised. Similarly we get the constraints |X 2Β·i+1 -X 2Β·i+3 |>2 (0≀iβ‰€βŒŠn-3 2βŒ‹) and |X 2Β·i -X 2Β·i+2 |>2 (1≀iβ‰€βŒŠn-2 2βŒ‹). Again we obtain two πšœπš–πš˜πš˜πšπš‘ constraints of the form πšœπš–πš˜πš˜πšπš‘(⌊n-1 2βŒ‹,2,〈X 1 ,X 3 ,β‹―,X n-1+n mod 2 βŒͺ) and πšœπš–πš˜πš˜πšπš‘(⌊n-2 2βŒ‹,2,〈X 2 ,X 4 ,β‹―,X n-n mod 2 βŒͺ).

Finally, the πš’πš—πšŸπšŽπš›πšœπšŽ constraint can also be used as a channelling constraint if we want to create an additional variable for each row. This may be for instance the case if we want to have a heuristics for selecting first the column or the row that has the smallest number of possibilities.

Figure 3.7.44. The unique solution to the 10-Amazons problem (modulo symmetries)

FigureΒ 3.7.44 shows the unique solution, modulo symmetries, to the n-Amazons problem for n=10. We have the following conjunction of constraints: