我想使用约束来解决以下问题,但实际上我不知道从哪里开始,所以我决定在这里发布以寻求帮助。
*** Fitting squares ***
Given the set of black squares of Figure 1 (a 2x2, 3x3, 4x4 and a 5x5 square),
fit them all into the white rectangle of Figure 1 (a 7x9 rectangle), and this in
such a way that there is no overlap between the squares.
Note that the black squares can only be put on integer coordinates.
Formulate the problem above as a constraint problem. Come up with a useful
representation of the problem in terms of the constraint processing tool.
Provide an explanation of indices, variables and domains. Furthermore,
provide for every introduced constraint,
the meaning of the constraint in natural language.
请这不是作业,因为我自己已经解决了添加正方形和圆形的问题。但这一个我不知道如何以及从哪里开始。作为初学者,我正在学习这个约束的东西,根本不知道如何解决这个问题,需要帮助。我假设使用以下语法来定义变量和约束:
*变量*
1)
名称必须以大写 [AZ] 开头,并且只能使用 [A-Za-z0-9_]。示例:X 或 MyVar_1。
2)
域是 [from,...,to] 范围内所有整数的集合。确保从 ≤ 到。
3)
索引是指索引变量的(单个!)索引。例如,如果您为变量“X”输入从 1 到 8 的索引范围,则“X(1)”、“X(2)”、...、“X(8)”中的每一个都是普通变量具有相同的域。指定索引范围,使得从 ≤ 到。如果您将“索引”字段留空,则假定您的变量是非索引的。(注意:使用 from = to 是可能的,尽管它没有多大意义:您可以使用非索引变量。)不要使用相同的名称两次,也不要使用一个普通名称和一次索引变量!也不要重用变量名的一部分,例如如果你已经有 MyVar_1,也不要使用 Var。
约束
如果需要,您可以输入算术约束,并为已使用的索引指定范围。算术约束的形式为 Expr ∼ Expr,其中 Expr 是使用整数、声明的变量和一些算术的表达式,其中 ∼ 是关系运算符。
1)
使用索引变量时,必须给出索引
- 在 MyVar(index) 格式中,即在变量名后面使用“(”和“)”,中间没有空格。
- 请注意,索引必须是变量,因此不允许使用类似 MyVar(37) 的内容。改为写 MyVar(i),并输入 i=37 的范围。
- 此外,索引必须出现在“范围”字段中。提示:如果您的约束必须在整个索引范围内保持不变,例如 i=1..10,那么只需输入一个简单满足的范围,例如 i>0。
- 索引名称可以按原样出现在约束中,即不作为索引。
- MyVar(index+x) 或 MyVar(index-x) 格式也是允许的,其中 x 是一个整数。不要在“+”或“-”之前或之后使用空格! 2)
算术使用运算符“+”、“-”、“*”、“/”、“mod”,其中“X / Y”是 X 和 Y 的商(向下舍入)。还允许使用“min(X,Y)”、“max(X,Y)”、“abs(X)”。
3) 可用的关系运算符有'='、'\='、'<'、'>'、'=<'、'>=',含义明显。
4) 使用圆括号消除歧义!示例:X(i) + Y(j) < 12 或 min(X(i),X(j)) \= Z 或 X(i) * i = 20。
也可以使用布尔表达式。允许的布尔连接词是 '<=>'、'=>'、'/\' 和 '\/',分别表示等价、蕴涵、合取和析取。
范围是一个表达式,其中包含约束中使用的每个索引。示例:i < j 或 i = j 或 (i = j /\ k \= l)。范围表达式不应包含“<=>”、“=>”或“\/”。注意:范围是一个逻辑表达式(隐式普遍量化),而不是像 i=1..10 之类的集合表达式!
以下示例使用上述语法:
You can solve, e.g., some linear integer equations using normal variables only:
Name: X, domain: 1..10000
Name: Y, domain: 1..10000
Name: Z, domain: 1..1000000
Constraint: 29*X + 43*Y = Z
Constraint: X * Y = Z
Another example is the N-queens problem which uses index variables:
Name: Q(i), i=1..4, domain: 1..4
Constraint: Q(i) \= Q(j), range: i < j
Constraint: abs(Q(i) - Q(j)) \= j - i, range: i < j
谢谢你的帮助。