Need Help In Solving A Constraint Problem

Question

I would like to solve the following problem using constraints but i 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.

   Explain 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. I am learning this constraint stuff as a beginner and don't know how to solve this one at all and need help. Am supposes to use the following syntax to define the variables and constraints:

* VARIABLES*

1. The name has to start with uppercase [A-Z], 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,..., too]. Make sure that from ≤ to.

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

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

• in the format MyVar(index), i.e. use "(" and ")" right behind the variable name, and with no spaces in-between.

• Note that the 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. 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. The available relational operators are '=', '\=', '<', '>', '=<', '>=', with obvious meanings.

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

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

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.

Answer 1

Let us assume there is a square of dimensions i*i(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 area 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 only happens 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