• $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$,

• $\mathrm{𝚍𝚒𝚏𝚏𝚗}$,

• $\mathrm{𝚐𝚎𝚘𝚜𝚝}$.

A constraint that can be used for modelling the squared squares problem [CroftFalconerGuy91] [LintWilson92] (also called the perfect squared squares problem [Duijvestijn78]): a perfect squared square of order $n$ is a square that can be tiled with $n$ smaller squares such that each of the smaller squares has a different integer size. It is called simple if it does not contain a subset of at least two squares, corresponding to a square or to a rectangle. Duijvestijn has shown in 1962 that no instances exist with less than 21 squares [Duijvestijn78]. A single solution depicted by Figure 3.7.71 exists with 21 squares, where the squares have sizes 2, 4, 6, 7, 8, 9, 11, 15, 16, 17, 18, 19, 24, 25, 27, 29, 33, 35, 37, 42, 50 and must be packed into a square of size 112.

Figure 3.7.71. A simple perfect squared square of order 21

A catalogue of such simple squared squares of orders 21 through 25 is provided in [BouwkampDuijvestijn92]. The following table contains all the problem instances from the previous catalogue. The different fields respectively give the problem number, the number of squares, the size of the master square and a list of the square sizes. The two last columns present a solution as a ground instance of geost, and a graphical view (see the description below). Problems 166 and 167, 168 and 169, 182 and 183 are identical, but have two non-isomorphic solutions. A much bigger table can be found at the following link http://www.squaring.net/.

When the size of the squares is known four constraint programming approach are respectively reported in [AggounBeldiceanu93], in [VanHentenryck94], in [SimonisBourreauBeldiceanu99], in [BeldiceanuCarlssonPoderSadekTruchet07] and in [BeldiceanuCarlssonPoder08].

For each squared square instance, the graphical view shows:

• root: the status just after posting the $\mathrm{𝚐𝚎𝚘𝚜𝚝}$ constraint,

• left branch: the status just after the last node on the leftmost branch of the search tree,

• trashing: the status at the first node of the search tree where trashing occurs (i.e. trashing occurs at a given node if we do not immediately fail at this node but we immediately fail on all children of that node).

Within the context of root and trashing, each graphical view from left to right consists of:

1. A two-dimensional view, which displays the compulsory part of the squares. In this context a square has a compulsory part if it has a compulsory part on both dimensions. Completely fixed squares are coloured in light grey or white, while not completely fixed squares are coloured in light red.

2. A cumulative view on the first dimension, which displays the squares that have a compulsory part with respect to the first dimension. Yellow squares correspond to squares that have a compulsory part in the first dimension but no compulsory part in the second dimension. All squares that are below the fat yellow profile correspond to squares for which the origin in the first dimension is fixed.

3. A cumulative view on the second dimension, which displays the squares that have a compulsory part with respect to the second dimension. Orange squares correspond to squares that have a compulsory part in the second dimension but no compulsory part in the first dimension. All squares that are below the fat orange profile correspond to squares for which the origin in the second dimension is fixed.

Within the context of left branch, each graphical view consists of similar graphic views. The only difference is that these views show how the compulsory part of an object increases as we go down a branch of the search tree. In this context the additional part of the compulsory part of an object is coloured in lighter blue as we go down a branch. This allows to see how the compulsory part of an object increases along a branch of the search tree. Finally not fat profile is shown in this context since we would have too many of them (i.e., one for each node of the path).

Let us comment the view associated with the first instance of the squared squares problems:

1. In the context of root, the biggest square (i.e., the light red square labelled with a 1) has a compulsory part thanks to the symmetry constraint. It also has a compulsory part with respect to the first dimension (note that we draw a rectangle since we consider the full height of the corresponding square). Finally it also has a compulsory part with respect to the second dimension.

   Figure 3.7.72. the root view for instance squared_squares_001

   

2. In the context of trashing, the biggest square (i.e., the white square labelled with a 1) is completely fixed at the lower leftmost corner of the  placement space. The second biggest square (i.e., the light red square labelled with a 2) is not completely fixed but has a compulsory part in both dimensions. Finally a third square has a tiny compulsory part. We retrieve these three squares in the cumulative views associated with the first and second dimension. Finally, within the cumulative view associated with the first dimension we also have a yellow square labelled with 8, which corresponds to a square that only has a compulsory part in the first dimension. On the one hand, the fat yellow profile corresponding to the first dimension consists of the three squares 1, 3, 8, which are completely fixed with respect to the first dimension. On the other hand the fat orange profile corresponding to the second dimension consists of the two squares 1 and 2.

   Figure 3.7.73. the trashing view for instance squared_squares_001

   

3. In the context of left branch, we can observe how the compulsory part grows as we go down the leftmost branch of the search tree. For instance at the root node we have a small compulsory part for the biggest square (i.e., the square labelled by 1). Then, as we go down the leftmost branch, this compulsory part gradually increases until the square becomes completely fixed in the next two steps. We can also observe that the heuristics tends to gradually create compulsory parts on the cumulative view associated with the first dimension (in light blue on the second picture).

   Figure 3.7.74. the left branch view for instance squared_squares_001