制約を使用して次の問題を解決したいのですが、実際にはどこから始めればよいかわからないため、ここに投稿して助けを求めることにしました。
*** 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] 内のすべての整数のセットです。from ≤ to であることを確認してください。
3)
インデックスは、インデックス付き変数の (単一の!) インデックスを参照します。たとえば、変数「X」に 1 から 8 までのインデックス範囲を入力すると、「X(1)」、「X(2)」、...、「X(8)」のそれぞれが通常の変数になります。同じドメインで。インデックスの範囲は ～ ≦ ～ となるように指定してください。「インデックス」フィールドを空白のままにすると、変数はインデックスのないものと見なされます。(注: from = to を使用することは可能ですが、あまり意味がありません。代わりに、インデックスのない変数を使用できます。) 同じ名前を 2 回使用しないでください。インデックス変数！また、変数名の一部を再利用しないでください。たとえば、既に MyVar_1 がある場合は、Var も使用しないでください。
制約
必要に応じて、使用されているインデックスの範囲を指定して、算術制約を入力できます。算術制約は Expr ∼ Expr の形式です。ここで、Expr は整数、宣言された変数、およびいくつかの演算を使用する式であり、~ は関係演算子です。
1)
インデックス付き変数を使用する場合、インデックスを指定する必要があります
- MyVar(index) の形式で、つまり、変数名の直後に「(」と「)」を使用し、間にスペースを入れないでください。
- 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
ご協力いただきありがとうございます。