需要帮助解决的约束问题 [英] Need Help In Solving A Constraint Problem

问题描述

我想使用约束来解决下面的问题，但我居然不知道从哪里开始，所以我决定将它张贴在这里寻求帮助。

I would like to solve the following problem using constraints but i actually don't know where to begin so i decided to post it here for help.

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

请这不是一门功课，因为我已经解决了将正方形和圆形自己。但是这一个我不知道如何和从哪里开始。正在学习这个约束的东西，一个初学者，不知道如何解决这个问题一个在所有需要帮助。我想用下面的语法定义变量和约束：

Please this is not a homework, because i have solved adding squares and circles myself. but this one i don't know how and where to start. Am learning this constraint stuff as a beginner and doesn't know how to solve this one at all and need help. Am suppose to use the following syntax to define the variables and constraints:

*变量*

1）

名称已经开始与大写[AZ]，只有用[A-ZA-Z0-9 _]。 举例：X或MyVar_1

Name has to start with uppercase [A-Z], and use only [A-Za-z0-9_]. Examples: X or MyVar_1.

2）

域的范围是集合所有整数[从...到。确保从≤到。

Domain is the set of all integers in the range [from,...,to]. Make sure that from ≤ to.

3）

索引指索引变量（单！）指数。例如，如果输入的索引范围是从1至8的变量X的，则每个的X（1），X（2），...，X（8），是一个正常的可变具有相同的域。指定索引范围，使得从≤到。如果您留空的索引的字段，你的变量被认为是一个非索引之一。 （注：从=使用到是可能的，但它不会使一大堆的道理：你可以使用一个非索引变量来代替。） 不要使用相同的名称两次，也没有一个是正常的，一旦一个索引变量！也不要重复使用变量名的一部分，例如如果你已经有MyVar_1，不要用无功也。

Index refers to the (single!) index of an indexed variable. For instance, if you enter an index range from 1 till 8 for variable "X", then each of "X(1)", "X(2)", ..., "X(8)" is a normal variable with the same domain. Specify the index range such that from ≤ to. If you leave blank the "Index" fields, your variable is assumed to be a non-indexed one. (Note: using from = to is possible, though it does not make a whole lot of sense: you could use a non-indexed variable instead.) Do not use the same name twice, also not one for a normal and once for an indexed variable! Also do not reuse part of variable names, e.g. if you already have MyVar_1, do not use Var also.

约束的

CONSTRAINTS

可以输入算术约束，如果需要的话与一系列规范已经使用的索引。算术约束的形式是Expr的〜Expr的，其中expr是使用整数，声明的变量一名前pression，以及一些算术，并在那里〜是关系运算符。

You can enter arithmetic constraints, if needed with a range specification for the indices that have been used. An arithmetic constraint is of the form Expr ∼ Expr, where Expr is an expression using integers, the declared variables, and some arithmetic, and where ∼ is a relational operator.

1）

在使用索引变量，指标必须给出

When using an indexed variable, an index must be given

• 在格式为MyVar（指数），即用（和）变量名后面的权利，并且不带空格其间。
• 请注意，索引必须是一个变量，所以像MyVar的（37）是不允许的。写为MyVar（我）来代替，并输入一系列的I = 37。
• 此外，该指数则必须出现在范围字段。提示：如果你的约束必须持有整个索引范围，如我= 1..10，然后只需输入一个平凡满意的范围内，如I> 0
• 在索引的名字可以出现在一个约束，即不为指标。
• 的格式为MyVar（指数+ X）或MyVar的（索引-x）时也是允许的，其中x是整数。之前或之后+或不要使用空格' - '！ 2）

• in the format MyVar(index), i.e. use "(" and ")" right behind the variable name, and with no spaces inbetween.
• Note that index must be a variable, so something like MyVar(37) is not allowed. Write MyVar(i) instead, and enter a range of i=37.
• Also, the index then must appear in the "range" field. Hint: if your constraint has to hold for the whole index range, e.g. i=1..10, then just enter a trivially satisfied range such as i>0.
• An index name can appear as is in a constraint, i.e. not as an index.
• the format MyVar(index+x) or MyVar(index-x) is also allowed, where x is an integer. Don't use spaces before or after '+' or '-'! 2)

算术运算符使用+， - ，*，/，mod，其中X / Y'是X和Y的商（向下取整）。还'分钟（X，Y）'，'最大值（X，Y）'，'绝对（X）'是允许的。

Arithmetic uses operators '+', '-', '*', '/', 'mod', where 'X / Y' is the quotient of X and Y (rounded downwards). Also 'min(X,Y)', 'max(X,Y)', 'abs(X)' are allowed.

3） 可用的关系运算符=，\ ='，'＆所述;'，'>'，'=＆所述;'，'> =，具有明显的含义

3) The available relational operators are '=', '\=', '<', '>', '=<', '>=', with obvious meanings.

4） 使用圆括号消除歧义！ 例子：X（ⅰ）+ Y（j）条所述＆; 12分钟或（X（i）中，X（j）条）\ = Z或X（ⅰ）* I = 20

4) Use round brackets to disambiguate! Examples: X(i) + Y(j) < 12 or min(X(i),X(j)) \= Z or X(i) * i = 20.

另外布尔前pressions都可以使用。允许布尔联结词是'＆LT; =>'，'=>'，'/ \'和'\ /'，等同性，言下之意，合取和析，分别为

Also boolean expressions can be used. Allowed boolean connectives are '<=>', '=>', '/\' and '\/', for equivalence, implication, conjunction and disjunction, respectively.

的范围是包含其用于约束的每个索引的当然pression。例如：I＆LT; J或I = J或（I =焦耳/ \ķ\ = 1）。一系列EX pression不应该包含'＆LT; =>'，'=>'，或'\ /'。 注：范围是一个逻辑EX pression（隐含普遍量化的），没有一套EX pression像我= 1..10

The range is an expression that contains each index which is used in the constraint. Examples: i < j or i = j or (i = j /\ k \= l). A range expression should not contain '<=>', '=>', or '\/'. Note: the range is a logical expression (implicitly universally quantified), not a set expression like i=1..10!

下面的示例使用上述语法：

The following example uses the above syntax:

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

感谢您的帮助。

Thanks for your help.

推荐答案

假设第i次;我平方（ⅰ= 2，3​​，4，或5）被放置成使得其左下角是以（X（ⅰ）中，Y（i））的。这样的方占用该区域从（x（i）中，Y（i））的左下方向（X（ⅰ）+ I，Y（I）+ I））在右上角。现在，你想说的是，J＆倍;Ĵ方不与这个广场重叠。出现这种情况只有当它处于完全的权利，完全向左，完全上面，或者完全低于这个广场。因此：

Suppose the i×i square (i=2, 3, 4, or 5) is placed such that its bottom left corner is at (X(i), Y(i)). So the square occupies the region from (X(i),Y(i)) in the bottom left to (X(i)+i,Y(i)+i)) in the top right. Now you want to say that the j×j square does not overlap with this square. This happens only when it lies entirely to the right, entirely to the left, entirely above, or entirely below this square. Thus:

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

这篇关于需要帮助解决的约束问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！