红帽全球峰会4.7. N queens
在一个 n 大小的象棋盘中放置 n 个皇后，没有两个皇后可以相互攻击。最常见的 n queens puzzle 是 8 个 queens puzzle，带有 n = 8 ：
约束：
- 使用 n 列的数量和 n 行。
- 将 n queens 放在按板上。
- 没有两个 queens 可以相互攻击。queen 可以在同一个水平、垂直或 diagonal 行中对任何其他 queen 进行攻击。
本文档主要使用 4 queens puzzle 作为主要示例。
建议的解决方案可以是：
图 4.1. 错误解决方案，用于 4 queens puzzle
以上解决方案是错误，因为 queens A1 和 B0 可以相互攻击（因此可能会 queens B0 和 D0）。删除 queen B0 会遵循 "no two queens 可相互攻击"约束，但会破坏 "place n queens" 约束。
以下是正确的解决方案：
图 4.2. Four queens puzzle 的正确解决方案
所有约束都已满足，因此解决方案正确。
请注意，大多数 queens puzzles 具有多个正确的解决方案。我们将专注于查找特定 n 的正确解决方案，而不是查找特定 n 可能的正确解决方案数量。
问题大小
4queens has 4 queens with a search space of 256. 8queens has 8 queens with a search space of 10^7. 16queens has 16 queens with a search space of 10^19. 32queens has 32 queens with a search space of 10^48. 64queens has 64 queens with a search space of 10^115. 256queens has 256 queens with a search space of 10^616.
n queens 示例的实现尚未优化，因为它作为 beginner 示例。然而，它可以轻松地处理 64 queens。通过一些更改，它已被显示，可以轻松地处理 5000 queens 等。
4.7.1. N queens 的域模型
本例使用域模型来解决四个 queens 问题。
创建域模型
良好的域模型将更方便地理解并解决您的规划问题。
这是 n queens 示例的域模型：
public class Column { private int index; // ... getters and setters }public class Row { private int index; // ... getters and setters }public class Queen { private Column column; private Row row; public int getAscendingDiagonalIndex() {...} public int getDescendingDiagonalIndex() {...} // ... getters and setters }计算搜索空间.
Queen实例有一个Column（例如： 0 是列 A, 1 is column B, …） 和一个Row（例如，0 为行 0，1 为行 1, …）。根据列和行计算升序行和降序行。
列和行索引从小时的左上角开始。
public class NQueens { private int n; private List<Column> columnList; private List<Row> rowList; private List<Queen> queenList; private SimpleScore score; // ... getters and setters }查找解决方案
单个
NQueens实例包含所有Queen实例的列表。它是解决方案实现，它将由 Solver 提供、解决并从 Solver 检索。
请注意，在四个 queens 示例中，NQueens getN （） 方法始终返回四个。
图 4.3. Four Queens 的解决方案
| columnIndex | rowIndex | ascendingDiagonalIndex (columnIndex + rowIndex) | descendingDiagonalIndex (columnIndex - rowIndex) | |
|---|---|---|---|---|
| A1 | 0 | 1 | 1 (**) | -1 |
| B0 | 1 | 0 (*) | 1 (**) | 1 |
| C2 | 2 | 2 | 4 | 0 |
| D0 | 3 | 0 (*) | 3 | 3 |
当两个 queens 共享相同的列时，行或 diagonal 行（如 ASP 和(DSL)）可以相互攻击。
