需要幫助解決約束問題

Question

我想解決以下問題使用約束，但我實際上不知道從哪裏開始，所以我決定發佈它在這裏尋求幫助。

*** 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的（指數），即使用
• 「（」 和 「）」 的變量後面權名字，而且沒有空格。
• 請注意，索引必須是一個變量，所以像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 

感謝您的幫助。

Answer 1

假設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