I would like to solve the following problem using restrictions, but I really don’t know where to start, so I decided to send it here for reference.
*** 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 homework, because I decided to add squares and circles. but this one I don’t know how and where to start. I am studying this restriction material as a beginner and do not know how to solve this problem at all and need help. Suppose you use the following syntax to define variables and constraints:
* VARIABLES *
1)
The name must begin with an uppercase [AZ] and use only [A-Za-z0-9_]. Examples: X or MyVar_1.
2)
A domain is a set of all integers in the range [from, ..., to]. Make sure from ≤ to.
3)
Index refers to the index (single!) Of the indexed variable. For example, if you enter a range of indices from 1 to 8 for the variable "X", then each of "X (1)", "X (2)", ..., "X (8)" is a normal variable with the same area. Specify a range of indices so that from ≤ to. If you leave the Index fields empty, your variable is considered unindexed. (Note: using from = to is possible, although this does not make much sense: you can use an unindexed variable instead.) Do not use the same name twice, also not one for a regular one and once for an indexed variable! Also, you should not reuse part of the variable names, for example. if you already have MyVar_1, do not use Var as well.
DIFFICULTIES
You can enter arithmetic restrictions, if necessary, with a range specification for the indices used. The arithmetic constraint has the form Expr ~ Expr, where Expr is an expression using integers, declared variables, and some arithmetic, and where ~ is a relational operator.
1)
When using an indexed variable, you must specify the index
- in the format MyVar (index), i.e. use "(" and ")" immediately after the variable name and without spaces between them.
- Note that the index must be a variable, so something like MyVar (37) is not allowed. Instead, write MyVar (i) and enter the range i = 37.
- In addition, the index should appear in the "range" field. Hint: if your constraint should be held for the entire range of indices, for example. i = 1.10, then just enter a trivially satisfactory range, such as i> 0.
- The index name can be displayed as specified in the restriction, i.e. not like an index.
- format MyVar (index + x) or MyVar (index-x) is also allowed, where x is an integer. Do not use spaces before or after the "+" or "-"! 2)
Arithmetic uses the operators '+', '-', '*', '/', 'mod', where 'X / Y' is the factor of X and Y (rounded down). Also allowed are "min (X, Y)", "max (X, Y)", "abs (X)".
3) Available relational operators: '=', '\ =', '<', '>', '= <', '> =', with obvious values.
4) Use parentheses to disambiguate! Examples: X (i) + Y (j) 12 or min (X (i), X (j)) \ = Z or X (i) * i = 20.
Boolean expressions can also be used. Valid logical connections are '<=>', '=>', '/ \' and '\ /' for equivalence, implication, conjunction and disjunction, respectively.
A range is an expression that contains every index that is used in a constraint. Examples: i <j or i = j or (i = j / \ k \ = l). The range expression must not contain '<=>', '=>' or '\ /'. Note: a range is a logical expression (implicitly universally quantified), and not a given expression, such as I = 1..10!
The following example uses the syntax above:
You can solve, eg, 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
Thank you for your help.