1. 示例概述

OptaPlanner 有几个例子。在本手册中，我们主要使用_n_ Queens 示例和云平衡示例进行说明。因此，建议至少阅读这些部分。

一些示例解决了学术竞赛中提出的问题。下表中的Contest列列出了比赛。它还确定了一个示例对于竞赛的目的是_现实_的还是_不现实的。**现实竞赛_是_官方的、独立的_竞赛：

• 这清楚地定义了一个真实的用例。

• 具有现实世界的约束。

• 具有多个真实世界的数据集。

• 期望在特定硬件的特定时间限制内可重现结果。

• 学术和/或企业运筹学社区的认真参与。

现实竞赛提供了 OptaPlanner 与竞争软件和学术研究的客观比较。

所有这些示例的源代码都可以在_示例/源_下的分发 zip 中获得 ，也可以在_optaplanner/optaplanner-examples_下的 git 中获得。

2. N 个皇后

2.1. 问题描述

将 n 个皇后放在一个 n 大小的棋盘上，这样没有两个皇后可以互相攻击。最常见的 n 个皇后谜题是八皇后谜题，其中 n = 8：

nQueens 截图

约束：

• 使用 n 列 n 行的棋盘。

• 在棋盘上放置 n 个皇后。

• 没有两个皇后可以互相攻击。皇后可以在同一水平、垂直或对角线上攻击任何其他皇后。

本文档大量使用四皇后拼图作为主要示例。

建议的解决方案可能是：

部分解决了 NQueens04 解释

图 1. 四皇后拼图的错误解决方案

上述解决方案是错误的，因为皇后 A1 和 B0 可以相互攻击（皇后 B0 和 D0 也可以攻击）。删除皇后 B0 将尊重“没有两个皇后可以相互攻击”的约束，但会打破“放置 n 个皇后”的约束。

以下是正确的解决方案：

解决了 NQueens04

图 2.四皇后难题的正确解决方案

所有约束条件都已满足，因此解决方案是正确的。

注意，大多数 n 皇后谜题都有多个正确答案。我们将重点寻找给定 n 的单个正确解，而不是给定 n 的可能正确解的数量。

2.2. 问题的复杂度

4queens 有 4 个 queens，搜索空间为 256。

8queens 有 8 个 queens，搜索空间为 10^7。

16queens 有 16 个 queens，搜索空间为 10^19。

32queens 有 32 个 queens，搜索空间为 10^48。

64 个皇后有 64 个皇后，搜索空间为 10^115。

256 个皇后有 256 个女王，搜索空间为 10^616。

n 皇后示例的实现尚未优化，因为它是一个初学者示例。然而，它可以轻松处理 64 个皇后。经过一些改动，它可以轻松处理 5000 个蜂王和更多蜂王。

2.3. 领域模型

这个例子使用域模型来解决四皇后问题。

1.创建域模型一个好的域模型将使您更容易理解和解决规划问题。这是 n 个皇后示例的域模型：

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}

2.计算搜索空间.

A Queen instance has a Column (for example: 0 is column A, 1 is column B, …) and a Row (its row, for example: 0 is row 0, 1 is row 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}

3.寻找解决方案

单个NQueens实例包含所有Queen实例的列表。它是提供给Solver.

请注意，在四个皇后示例中，NQueens 的getN()方法将始终返回四个。