PyCSP3 v2.0（2021 年 12 月 15 日）

这是 PyCSP3 的 2.0 版，Python 3（3.6 版或更高版本）中用于建模组合约束问题的库；见www.pycsp.org。PyCSP3 的灵感来自JvCSP3（一种基于 Java 的 API）和Numberjack。使用 PyCSP3，可以生成以下实例：

1. CSP（约束满足问题）
2. COP（约束优化问题）

XCSP3 格式；见www.xcsp.org。目前，PyCSP3 针对XCSP3-core，它允许我们使用整数变量（具有有限域）和流行的约束。

注意：

• 一个包含 60 多个 Jupyter 笔记本的专用网站可用
• 有详细记录的指南可用
• PyCSP3 作为PyPi 包提供

在这个阶段，可以运行两个嵌入式求解器：

• 约束求解器ACE (AbsCon Essence)，带有选项 -solve 或选项 -solver=ace
• 约束求解器Choco，带有选项 -solver=choco

有关如何试用这些嵌入式求解器的信息，请参阅本文档。

当然，可以在生成的 XCSP3 实例（文件）上启动任何识别 XCSP3 格式的求解器。例如，可以立即在 XCSP3 实例（文件）上运行 ACE 或 Choco，因为相应的可执行文件（jar 文件）存在于目录pycsp3/solvers/ace和 pycsp3/solvers/choco. 例如，要在 XCSP3 实例“zebra.xml”上运行 ACE，只需执行：

java -jar ACE-YY-MM.jar zebra.xml 

同时将 YY 和 MM 替换为 jar 文件名称中存在的当前值。

请注意，也可以使用 Python 引导求解器；请参阅PyCSP3 求解过程。

1) 从 PyPi 安装

这是安装 PySCP3 的最简单方法。

请注意，您需要先安装 Python 3（3.6 版或更高版本）。例如，您可以从python.org 执行此操作

安装 PyCSP3 (Linux)

检查是否安装了“pip3”。如果不是这种情况，请执行：

sudo apt install python3-pip

然后，使用命令“pip3”安装 PyCSP3：

sudo pip3 install pycsp3

要使用 -solve 或 -solver 选项，您需要安装 Java（至少，版本 11）：

sudo apt-get install openjdk-11-jdk

安装 PyCSP3 (Mac OS)

如果您的系统上安装了 Python 3，则命令“pip3”应该已经存在。

使用命令“pip3”安装 PyCSP3：

sudo pip3 install pycsp3

要使用 -solve 或 -solver 选项，您需要安装 Java（至少版本 11）。

安装 PyCSP3 (Windows)

您可能需要升级“点子”。打开控制台并输入：

python -m pip install --upgrade pip

然后，要安装 pycsp3，请键入：

python -m pip install pycsp3

要使用 -solve 或 -solver 选项，您需要安装（至少）Java 版本 11：

https://www.oracle.com/java/technologies/javase-downloads.html

并在 PATH 中添加 java 命令，例如，暂时使用以下命令：

set path=%path%;C:/Program Files/Java/jdk-14.0.1/bin/

您可以通过在控制台中键入来检查 java 命令：

java --version

更新 PyCSP3 的版本（用于 PyPi）

要更新您的 PyCSP3 版本，只需执行：

对于 Linux/Mac：

sudo pip3 install --upgrade pycsp3

对于 Windows：

python -m pip install --upgrade pycsp3

复制模型池

PyCSP3 附带了 100 多个模型。要将它们放在problems当前目录的子目录中，请执行：

python3 -m pycsp3 (For linux/Mac)
python -m pycsp3 (For Windows)

您可以测试其中一个模型的编译，例如：

python3 problems/csp/single/Zebra.py (For Linux/Mac)
python problems\csp\single\Zebra.py (For Windows)

2）从GitHub克隆安装（替代）

PyPi 的替代方法是从 GitHub 克隆代码。这是 MAC OS 的插图。我们假设安装了 Python 3（否则，port install python38例如键入），因此也安装了“pip3”。在控制台中，键入：

git clone https://github.com/xcsp3team/pycsp3.git
pip3 install lxml

您可能需要更新环境变量“PYTHONPATH”，例如输入：

export PYTHONPATH=$PYTHONPATH:.

3) 编译和示例

我们简洁地介绍了几个 PyCSP3 模型，展示了如何使用不同的选项来编译它们。但是，请注意www.pycsp.org上提供了许多插图，尤其是许多带有 Jupyter 笔记本的模型。

首先，我们提供一些关于编译的一般信息。

编译 PyCSP3 模型

要从 PyCSP3 模型生成 XCSP3 实例，您必须执行：

python3 <file> [options]

和：

• <file>：要执行的 Python 文件，描述 PyCSP3 中的模型
• [options]：编译时可能使用的选项

在这些选项中，我们发现：

• -data=<data_value>：允许我们指定模型要使用的数据。有可能：

  • 初级：-数据=5
  • 一个简单的列表：-data=[9,0,0,3,9]
  • 一个 JSON 文件：-data=Bibd-3-4-6.json

  然后可以通过预定义变量在 PyCSP3 模型中直接使用数据data。

• -dataparser=<file>：一个 Python 文件，用于读取/解析以任意形式（例如，通过文本文件）给出的数据。有关说明，请参见下面的示例非图。

• -dataexport：以 JSON 格式导出（保存）数据。有关说明，请参见下面的示例非图。

• -variant=<variant_name>: 变体的名称，与 function 一起使用variant()。有关说明，请参见下面的示例 AllInterval。

• -solve：尝试使用嵌入式求解器“Ace”求解实例。它要求安装 Java 版本 8（至少）。

• -solver=<solver_name>: 尝试使用给定名称的求解器求解实例。目前，它可以是“ace”或“choco”。重要提示：它要求安装 Java 版本 8（至少）。有关如何试用这些嵌入式求解器的信息，请参阅本文档。

• -output=<file_name>：设置生成的 XCSP3 实例的文件名（考虑扩展名 .xml）

默认情况下，会生成一个包含 XCSP3 实例的文件，除非您使用以下选项：

• -display：在系统标准输出中显示 XCSP3 实例，而不是生成 XCSP3 文件

示例 1：在控制台模式下

我们的第一个示例展示了如何在控制台模式下构建基本模型。在这个例子中，我们只发布了两个变量和两个简单​​的二元约束。

$ python3
Python 3.5.2
>>> from pycsp3 import *
>>> x = Var(range(10))
>>> y = Var(range(10))
>>> satisfy(
       x < y,
       x + y > 15
    )
>>> compile()

请注意，要获取 XCSP3 文件，我们调用compile().

示例 2：发送+更多=钱

此示例显示了在不需要用户提供数据时如何定义模型。这是经典的加密算术难题“发送+更多=金钱”。

文件SendMore.py

from pycsp3 import *

# letters[i] is the digit of the ith letter involved in the equation
s, e, n, d, m, o, r, y = letters = VarArray(size=8, dom=range(10))

satisfy(
    # letters are given different values
    AllDifferent(letters),

    # words cannot start with 0
    [s > 0, m > 0],

    # respecting the mathematical equation
    [s, e, n, d] * [1000, 100, 10, 1]
    + [m, o, r, e] * [1000, 100, 10, 1]
    == [m, o, n, e, y] * [10000, 1000, 100, 10, 1]
)

要生成 XCSP3 实例（文件），命令是：

python3 SendMore.py

要生成和解决（使用 ACE）XCSP3 实例，命令是：

python3 SendMore.py -solve

要使用 Choco 生成和求解 XCSP3 实例，命令是：

python3 SendMore.py -solver=choco

示例 3：全区间系列

这个例子展示了如何简单地为模型指定一个整数（作为唯一数据）。为了我们的说明，我们考虑问题All-Interval Series。

一个经典模型是：

文件AllInterval.py（版本 1）

from pycsp3 import *

n = data

# x[i] is the ith note of the series
x = VarArray(size=n, dom=range(n))

satisfy(
    # notes must occur once, and so form a permutation
    AllDifferent(x),

    # intervals between neighbouring notes must form a permutation
    AllDifferent(abs(x[i] - x[i + 1]) for i in range(n - 1)),

    # tag(symmetry-breaking)
    x[0] < x[n - 1]
)

symmetry-breaking请注意将直接集成到由以下命令生成的 XCSP3 文件中的标记的存在：

python3 AllInterval.py -data=5

假设您希望声明第二个变量数组来表示连续距离。这将给出：

文件AllInterval.py（版本 2）

from pycsp3 import *

n = data

# x[i] is the ith note of the series
x = VarArray(size=n, dom=range(n))

# y[i] is the distance between x[i] and x[i+1]
y = VarArray(size=n - 1, dom=range(1, n))

satisfy(
    # notes must occur once, and so form a permutation
    AllDifferent(x),

    # intervals between neighbouring notes must form a permutation
    AllDifferent(y),

    # computing distances
    [y[i] == abs(x[i] - x[i + 1]) for i in range(n - 1)],

    # tag(symmetry-breaking)
    [x[0] < x[n - 1], y[0] < y[1]]
)

但是，有时，将模型的不同变体组合在同一个文件中可能是相关的。在我们的示例中，这将给出：

文件AllInterval.py（版本 3）

from pycsp3 import *

n = data

# x[i] is the ith note of the series
x = VarArray(size=n, dom=range(n))

if not variant():

    satisfy(
        # notes must occur once, and so form a permutation
        AllDifferent(x),

        # intervals between neighbouring notes must form a permutation
        AllDifferent(abs(x[i] - x[i + 1]) for i in range(n - 1)),

        # tag(symmetry-breaking)
        x[0] < x[n - 1]
    )

elif variant("aux"):

    # y[i] is the distance between x[i] and x[i+1]
    y = VarArray(size=n - 1, dom=range(1, n))

    satisfy(
        # notes must occur once, and so form a permutation
        AllDifferent(x),

        # intervals between neighbouring notes must form a permutation
        AllDifferent(y),

        # computing distances
        [y[i] == abs(x[i] - x[i + 1]) for i in range(n - 1)],

        # tag(symmetry-breaking)
        [x[0] < x[n - 1], y[0] < y[1]]
    )

对于编译主模型（变体），命令是：

python3 AllInterval.py -data=5

为了编译第二个模型变体，使用选项-variant，命令是：

python3 AllInterval.py -data=5 -variant=aux

要生成和求解（使用 ACE）10 阶和变体“aux”的实例，命令是：

python3 AllInterval.py -data=10 -variant=aux -solve

示例 4：BIBD

此示例说明如何指定整数列表用作模型的数据。为了我们的说明，我们考虑问题BIBD。我们需要五个整数v, b, r, k, l来指定一个唯一的实例（可能，b并且r可以设置为 0，以便根据此问题的模板自动计算这些值）。型号为：

文件Bibd.py

from pycsp3 import *

v, b, r, k, l = data
b = (l * v * (v - 1)) // (k * (k - 1)) if b == 0 else b
r = (l * (v - 1)) // (k - 1) if r == 0 else r

# x[i][j] is the value of the matrix at row i and column j
x = VarArray(size=[v, b], dom={0, 1})

satisfy(
    # constraints on rows
    [Sum(row) == r for row in x],

    # constraints on columns
    [Sum(col) == k for col in columns(x)],

    # scalar constraints with respect to lambda
    [row1 * row2 == l for (row1, row2) in combinations(x, 2)]
)

要生成 XCSP3 实例（文件），我们可以执行如下命令：

python3 Bibd.py -data=[9,0,0,3,9]

使用某些命令解释器（shell），您可能必须转义字符 '[' 和 ']'，这给出：

python3 Bibd.py -data=\[9,0,0,3,9\]

示例 5：机架配置

此示例说明如何指定 JSON 文件用作模型的数据。为了我们的说明，我们考虑问题Rack Configuration。然后最初在 JSON 文件中给出数据（针对特定实例），例如：

文件Rack_r2.json

{
    "nRacks": 10,
    "models": [[150,8,150],[200,16,200]],
    "cardTypes": [[20,20],[40,8],[50,4],[75,2]]
}

在下面的模型中，我们直接解包变量的组成部分data（因为它是自动以命名元组的形式给出的），其字段正是 JSON 文件中主要对象的字段。

文件Rack.py

from pycsp3 import *

nRacks, models, cardTypes = data
models.append([0, 0, 0])  # we add first a dummy model (0,0,0)
powers, sizes, costs = zip(*models)
cardPowers, cardDemands = zip(*cardTypes)
nModels, nTypes = len(models), len(cardTypes)

table = {(i, powers[i], sizes[i], costs[i]) for i in range(nModels)}

# m[i] is the model used for the ith rack
m = VarArray(size=nRacks, dom=range(nModels))

# p[i] is the power of the model used for the ith rack
p = VarArray(size=nRacks, dom=powers)

# s[i] is the size (number of connectors) of the model used for the ith rack
s = VarArray(size=nRacks, dom=sizes)

# c[i] is the cost (price) of the model used for the ith rack
c = VarArray(size=nRacks, dom=costs)

# nc[i][j] is the number of cards of type j put in the ith rack
nc = VarArray(size=[nRacks, nTypes], dom=lambda i, j: range(min(max(sizes), cardDemands[j]) + 1))

satisfy(
    # linking rack models with powers, sizes and costs
    [(m[i], p[i], s[i], c[i]) in table for i in range(nRacks)],

    # connector-capacity constraints
    [Sum(nc[i]) <= s[i] for i in range(nRacks)],

    # power-capacity constraints
    [nc[i] * cardPowers <= p[i] for i in range(nRacks)],

    # demand constraints
    [Sum(nc[:, j]) == cardDemands[j] for j in range(nTypes)],

    # tag(symmetry-breaking)
    [Decreasing(m), imply(m[0] == m[1], nc[0][0] >= nc[1][0])]
)

minimize(
    # minimizing the total cost being paid for all racks
    Sum(c)
)

要生成 XCSP3 实例（文件），我们执行以下命令：

python3 Rack.py -data=Rack_r2.json

可能希望 JSON 文件中的数据具有另一种结构，例如：

文件Rack_r2b.json

{
    "nRacks": 10,
    "rackModels": [
	{"power":150,"nConnectors":8,"price":150},
	{"power":200,"nConnectors":16,"price":200}
    ],
    "cardTypes": [
	{"power":20,"demand":20},
	{"power":40,"demand":8},
	{"power":50,"demand":4},
	{"power":75,"demand":2}
    ]
}

我们只需要从之前的模型中修改一行：

文件Rack2.py

models.append(models[0].__class__(0, 0, 0))  # we add first a dummy model (0,0,0) ; we get the class of the used named tuples to build a new one

要生成 XCSP3 实例（文件），我们执行以下命令：

python3 Rack2.py -data=Rack_r2b.json

示例 6：非图

此示例说明如何使用辅助 Python 文件来解析最初未以 JSON 格式提供的数据。为了我们的说明，我们考虑问题Nonogram。数据（针对特定的 Nonogram 拼图）最初在文本文件中给出，如下所示：

1. 一行表示行数和列数，
2. 然后，对于每一行，一行说明块的数量，然后是所有这些块的大小（在同一行上），
3. 然后，对于每一列，一行说明块的数量，然后是所有这些块的大小（在同一行上）。

下面是这样一个文本文件的示例。

文件Nonogram_example.txt

24 24
0
1	5
2	3 3
2	1 2
2	2 1
2	1 1
2	3 3
3	1 5 1
3	1 1 1
3	2 1 1
3	1 1 2
3	3 1 3
3	1 3 1
3	1 1 1
3	2 1 2
3	1 1 1
1	5
3	1 1 1
3	1 1 1
3	1 1 1
3	5 1 1
2	1 2
3	2 2 4
2	4 9

0
0
0
1	1
1	2
1	2
2	6 1
3	3 1 3
3	1 1 4
4	2 1 1 7
5	1 1 1 1 1
3	1 12 1
5	1 1 1 1 1
4	2 1 1 7
4	1 1 4 1
4	2 1 2 2
2	8 3
2	1 1
2	1 2
1	4
1	3
1	2
1	1
0

首先，我们需要用 Python 编写一段代码来构建一个字典data，然后在我们的模型中使用该字典（在自动转换为命名元组之后）。我们必须首先从pycsp3.problems.data.parsing. 然后我们可以将任何新的任意项添加到字典data中（最初是空的）。这就是我们在下面对两个键称为rowPatterns和的项目所做的colPatterns。与这两个键关联的值被定义为整数的二维数组（列表），定义了块的大小。next_int()可以调用该函数来读取文本文件中的下一个整数，这将在命令行上指定（见下文）。

文件Nonogram_Parser.py

from pycsp3.problems.data.parsing import *

nRows, nCols = next_int(), next_int()
data["rowPatterns"] = [[next_int() for _ in range(next_int())] for _ in range(nRows)]
data["colPatterns"] = [[next_int() for _ in range(next_int())] for _ in range(nRows)]

然后，我们只需通过从变量中获取数据来编写模型data。该模型完全独立于最初给出数据的方式（例如，来自文本文件或 JSON 文件）。在下面的代码中，请注意如何根据Automaton指定的模式（块列表）定义对象。此外，对于regular约束，我们只需编写类似scope in automaton. 最后，x[:, j]表示 的第 j 列x。

文件Nonogram.py

from pycsp3 import *

rows, cols = data  # patterns for row and columns 
nRows, nCols = len(rows), len(cols)

def automaton(pattern):
    q = Automaton.q  # for building state names
    transitions = []
    if len(pattern) == 0:
        n_states = 1
        transitions.append((q(0), 0, q(0)))
    else:
        n_states = sum(pattern) + len(pattern)
        num = 0
        for i, size in enumerate(pattern):
            transitions.append((q(num), 0, q(num)))
            transitions.extend((q(num + j), 1, q(num + j + 1)) for j in range(size))
            transitions.append((q(num + size), 0, q(num + size + (1 if i < len(pattern) - 1 else 0))))
            num += size + 1
    return Automaton(start=q(0), final=q(n_states - 1), transitions=transitions)

# x[i][j] is 1 iff the cell at row i and col j is colored in black
x = VarArray(size=[nRows, nCols], dom={0, 1})

satisfy(
    [x[i] in automaton(rows[i]) for i in range(nRows)],

    [x[:, j] in automaton(cols[j]) for j in range(nCols)]
)

要生成 XCSP3 实例（文件），我们只需要指定文本文件的名称（选项-data）和 Python 解析器的名称（选项-dataparser）。

python3 Nonogram.py -data=Nonogram_example.txt -dataparser=Nonogram_Parser.py

也许，您认为将数据直接保存在 JSON 文件中会更简单。您可以使用选项生成这样的文件-dataexport。命令如下：

python3 Nonogram.py -data=Nonogram_example.txt -dataparser=Nonogram_Parser.py -dataexport

生成一个文件Nonogram_example.json，其内容为：

{
 “colPatterns” ：[[],[],[],[ 1 ],[ 2 ] ,[ 2 ] , [ 6,1 ] , [ 3,1,3 ] , [ 1,1,4 ] , [ 2 , 1 , 1 , 7 ],[ 1 , 1 , 1 , 1 , 1 ],[ 1 , 12 , 1 ],[ 1 , 1 , 1 , 1 , 1 ],[2、1、1、7 ] 、[ 1、1、4、1 ] 、[ 2、1、2、2 ] 、[ 8、3 ] 、[ 1、1 ] 、[ 1、2 ] 、[ 4 ] _ _ _ _ _ _ _ _ _ _ _ _ ,[ 3 ],[ 2 ],[ 1 ],[]],
 “行模式” ：[[]，[ 5 ] ，[ 3，3 ] ，[ 1，2 ] ，[ 2，1 ] ，[ 1，1 ] ，[ 3，3 ] ，[ 1，5，1 ] ， [ 1 , 1 , 1 ],[ 2 ,