3.6. N queens
在 n sized chessboard 上放置 N 个queens 数量,因此没有两个 queens 相互攻击。最常见的 n queens puzzle 是八个 queens puzzle,n = 8 :
约束:
- 使用 n 列和 n 行。
- 将 n queens 放置到 chessboard 上。
- 没有两个 queens 相互攻击。queen 可以在同一个横向、垂直或诊断行中互相攻击。
本文档主要使用 4 queens puzzle 作为主要示例。
建议的解决方案可以是:
图 3.1. 错误解决方案,用于 4 queens puzzle
以上解决方案错误,因为 queens A1
和 B0
可以相互攻击(从而可以相互攻击 B0
和 D0
)。删除 queen B0
会遵守"无两个 queens 可相互攻击"约束,但可能会破坏"place n queens"约束。
以下是正确的解决方案:
图 3.2. 用于 Four queens puzzle 的正确解决方案
满足了所有限制,因此解决方案正确。
请注意,最多 n 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 示例中的实现没有被优化,因为它作为初学者示例运行。然而,它可以轻松处理 64 个问题。随着一些更改,它已被显示,可以轻松地处理 5000 频率等。
3.6.1. N 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 一行,1 为行 1, …)。可以按列和行计算升序诊断行和降序诊断行。
列和行索引从 chessboard 的左上角启动。
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 检索的解决方案实施。
请注意,在四个 queens 示例中,NQueens getN ()
方法始终返回四个。
图 3.3. Four Queens 的解决方案
表 3.2. 域模型中的解决方案详情
columnIndex | rowIndex | atingDiagonalIndex (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 共享同一列时,行或诊断行,如 principal 和(**),他们可以相互攻击。