Нужна помощь в решении проблемы ограничения

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)

Индекс относится к (одиночному!) Индексу индексированной переменной. Например, если вы введете диапазон индекса от 1 до 8 для переменной "X", то каждый из "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 ", "=>" или "\/". Примечание: диапазон является логическим выражением (неявно универсально выраженным), а не выражением множества, как 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 (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