需要帮助解决约束问题

我想解决以下问题使用约束，但我实际上不知道从哪里开始，所以我决定发布它在这里寻求帮助。需要帮助解决约束问题

*** 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）

域是该范围内的所有整数的集合[从，...，至]。确保从≤到。

3）

指数指的是索引的变量的（单！）指数。例如，如果为变量“X”输入1到8的索引范围，那么“X（1）”，“X（2）”，...，“X（8）”中的每一个都是正常变量与相同的域名。指定从≤到的索引范围。如果您将“索引”字段留空，则您的变量被假定为非索引字段。（注意：使用from = to是可能的，尽管它没有多大意义：您可以改用非索引变量。）不要使用两次相同的名称，也不要使用一次用于正常和一次索引变量！也不要重用部分变量名称，例如如果你已经有MyVar_1，也不要使用Var。

约束

您可以输入算术限制，如果需要与已经使用了索引的范围规范。算术约束的格式为Expr〜Expr，其中Expr是一个使用整数，声明的变量和一些算术的表达式，其中〜是一个关系运算符。

1）

当使用索引变量，指数必须给予

“（” 和 “）” 的变量后面权名字，而且没有空格。
请注意，索引必须是一个变量，所以像MyVar（37）这样的东西是不允许的。改为写MyVar（i），然后输入i = 37的范围。
此外，索引必须出现在“范围”字段中。提示：如果您的约束必须适用于整个指数范围，例如我= 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 1 = 1）。范围表达式不应包含'< =>'，'=>'或'\ /'。注意：范围是一个逻辑表达式（隐式普遍量化），不是像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

感谢您的帮助。

来源

2011-05-15 Kap

假设i × i square（i = 2,3,4或5）放置成其左下角位于（X（i），Y（i））处。因此，该平方占据从左下角的（X（i），Y（i））到右上角的（X（i）+ i，Y（i）+ i））的区域。现在你想说的是，j × j平方不与这个正方形重叠。只有当它完全位于右侧，完全位于左侧，完全位于上方或完全位于该方形下方时才会发生。因此：

Name X(i), i=2..5, domain: 1..7 
Name Y(i), i=2..5, domain: 1..9 
Constraint: X(i)+i=<X(j) \/ X(j)+j=<X(i) \/ Y(i)+i=<Y(j) \/ Y(j)+j=<Y(i), range: i<j

来源

2011-05-15 11:04:04 ShreevatsaR

非常感谢您的回答 – Kap 2011-05-15 11:25:25

需要帮助解决约束问题

回答

相关问题