3.6. N queens

在一个 n 大小的象棋盘中放置 n 个皇后，没有两个皇后可以相互攻击。最常见的 n queens puzzle 是 8 个 queens puzzle，带有 n = 8 ：

约束：

使用 n 列的数量和 n 行。
将 n queens 放在按板上。
没有两个 queens 可以相互攻击。queen 可以在同一个水平、垂直或 diagonal 行中对任何其他 queen 进行攻击。

本文档主要使用 4 queens puzzle 作为主要示例。

建议的解决方案可以是：

图 3.1. 错误解决方案，用于 4 queens puzzle

以上解决方案是错误，因为 queens A1 和 B0 可以相互攻击（因此可能会 queens B0 和 D0）。删除 queen B0 会遵循 "no two queens 可相互攻击"约束，但会破坏 "place n queens" 约束。

以下是正确的解决方案：

图 3.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.

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.

Copy to Clipboard

Toggle word wrap

n queens 示例的实现尚未优化，因为它作为 beginner 示例。然而，它可以轻松地处理 64 queens。通过一些更改，它已被显示，可以轻松地处理 5000 queens 等。

3.6.1. N queens 的域模型
复制链接

本例使用域模型来解决四个 queens 问题。

创建域模型

良好的域模型将更方便地理解并解决您的规划问题。

这是 n queens 示例的域模型：

public class Column {

    private int index;

    // ... getters and setters
}

public class Column {

    private int index;

    // ... getters and setters
}

Copy to Clipboard

Toggle word wrap

public class Row {

    private int index;

    // ... getters and setters
}

public class Row {

    private int index;

    // ... getters and setters
}

Copy to Clipboard

Toggle word wrap

public class Queen {

    private Column column;
    private Row row;

    public int getAscendingDiagonalIndex() {...}
    public int getDescendingDiagonalIndex() {...}

    // ... getters and setters
}

public class Queen {

    private Column column;
    private Row row;

    public int getAscendingDiagonalIndex() {...}
    public int getDescendingDiagonalIndex() {...}

    // ... getters and setters
}

Copy to Clipboard

Toggle word wrap

计算搜索空间.

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
}

public class NQueens {

    private int n;
    private List<Column> columnList;
    private List<Row> rowList;

    private List<Queen> queenList;

    private SimpleScore score;

    // ... getters and setters
}

Copy to Clipboard

Toggle word wrap

查找解决方案
单个 NQueens 实例包含所有 Queen 实例的列表。它是 解决方案 实现，它将由 Solver 提供、解决并从 Solver 检索。

请注意，在四个 queens 示例中，NQueens getN （） 方法始终返回四个。

图 3.3. Four Queens 的解决方案

Expand

表 3.2. 域模型中解决方案详情
	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)）可以相互攻击。

返回顶部

3.6. N queens

3.6.1. N queens 的域模型
复制链接

学习

尝试、购买和销售

社区

关于红帽文档

让开源更具包容性

關於紅帽

Theme

Red Hat legal and privacy links

Red Hat legal and privacy links

3.6. N queens

3.6.1. N queens 的域模型复制链接链接已复制到粘贴板!

学习

尝试、购买和销售

社区

关于红帽文档

让开源更具包容性

關於紅帽

Theme

Red Hat legal and privacy links

Red Hat legal and privacy links

3.6.1. N queens 的域模型
复制链接