Menu

Compound Perfect Squared Squared Squares (CPSSs);
Orders 24 to 86

Compound Perfect Squared Squares (CPSSs) are squares dissected into smaller squares, all different integer sizes, but with a rectangular inclusion (or a dissected square) in the tiling. These squared squares are scarcer than SPSSs (with recent substitution methods, this is no longer the case; see CPSS orders 40+). A great deal of thought and ingenuity has gone into the devising of methods of construction of CPSSs. The order 24 CPSS by T.H. Willcocks was found many years ( published 1948) before computers were able to verify it was indeed the lowest order example of its kind. See Simple Perfect Squared Squares for a chronology of Perfect Squared Square discoveries.

Compound squared squares have often been created using methods called 'transforms'. There are many dozens of transforms and they are generally not computer assisted. A transform will often change one square tiling into another.

One method uses algebra to create a CPSS from existing simple squared rectangles by selecting a squared rectangle from the catalogue and designating one of the square elements as a rectangle of indeterminate width and height, then making the height and width of the squared rectangle equal (to make it square), and recalculating both the sizes of the squares and the sides of the included rectangle using elementary algebra. The solution will be unique and with luck another perfect squared rectangle may be found in the catalogue which is able to fit into the included rectangle without any repeated elements.

CPSSs can also be created by combining Simple Perfect Squared Rectangles (SPSRs) in a number of different ways. Two SPSRs of the same size with no elements in common can be combined to make CPSS. Two SPSRs of the same shape, scaled can be combined to make CPSS. Several SPSRs of different sizes and shapes, but satisfying certain relationships can be combined into CPSSs. A construction based on the Fibonacci sequence as element sizes has also been used to create CPSSs. Computers can be used to speed up some of these methods.

A computational approach is also possible where 2-connected planar graph embeddings are generated, then transformed into compound square tilings using electrical network analysis. These tilings are tested for CPSSs.

The author of this website, Stuart E. Anderson, has written a paper 'Compound Perfect Squared Squares of the Order Twenties' (2013). It is available from the Arxiv link. It gives some historical and technical detail on CPSS construction, including an extensive bibliography on the topic of squared squares. However this website provides a great many more dissection codes and illustrations, mainly because the website is not limited to the low-orders and to CPSSs in particular.

CPSS Isomers

Every CPSS is one of at least 4 isomers. The included compound rectangle can be positioned in 4 different ways. If the rectangle is trivially compound (has a square equal to the height or width of the rectangle) then the rectangle can be positioned in 8 ways, if the rectangle is doubly or triply trivially compound it can be positioned in 16 and 32 ways, and so on. Other kinds of compound construction are also possible. In pdf's and drop down menus, isomer number is shown with square id and discoverer id. The first couple of dozen different isomer counts for which we have examples are 4, 7, 8, 11, 12, 16, 19, 20, 23, 24, 28, 31, 32, 35, 36, 39, 40, 47, 48, 56, 60, 63, 64, 68, 72, 76, 80, 88, 96. By combining SPSR and SPSS isomers with the known CPSS isomers up to 96, we can create further CPSSs with isomer counts such as 112, 128, 132, 144, 152, 160, 176, 184, 192, 196, 224, 248, 256, 264, 288, 304, 320, 368, 384, 448, 456, 480, 496, 512, 544, 552, 576, 672, 744, 768, 864, 896, 1024, 1088, 1152, 1216, 1344, 1472, 1536, 1632, 1728, 1792, 1984, 2048, 4096. An isomer count of 7 is produced when 2 rectangles overlap with a common element, higher odd numbers of isomers are the result of overlaps and other arrangements. Geoffrey Morley has shown an isomer count of 14 is possible if suitable SPSRs can be found to construct a particular CPSS, so the sequence given above is expected to contain a number of such gaps where additional terms could be inserted. A linked pdf gives examples of all known isomer counts up to 96.

A chronology of the low(er) order compound perfect squared square (CPSS) discoveries and the people who made them;

CPSSs counts for orders 24 to 39 are now complete (subject to confirmation *).

* Proof of completeness for CPSS orders 33 to 39 is subject to proof of some conjectures used in the enumeration process. The results for orders 24 to 32 are identical to the previous results for these orders.

CPSSs counts by order are listed in the OEIS as sequences;

Credit for Discovery

The people listed below have published or have been credited with the discovery of compound squared squares.

Generating CPSSs from Electrical Network Graphs

Using Brendan McKay and Gunnar Brinkmann's plantri software, graph classes specified as 2-connected (exactly 2-connected, not at least 2-connected), minimum degree 3 (also known as homeomorphically irreducible - no vertex of degree 2 is permitted), simple planar maps in the sphere of up to 30 edges (graphs (v,f,e) where v ≤ f) have been enumerated and generated from the commandline ; Use

The 2-connected graphs and their dual graph classes, have different counts, but the duals dont need to be generated or processed for CPSSs.

Graph classes (v,f,e) and (f,v,e), where v + f = e + 2, are dual graph classes. The dual graph can be generated from the primary graph, and it produces the same tiling, so dual graphs dont need to be generated and processed, but there is a complication. With 2-connected maps, unlike 3-connected maps, the numbers of graph and dual classes produced by plantri are not identical. Graph class (v,f,e) where f > v, has lesser numbers than the dual graph class (f,v,e).

What is the nature of these extra graphs? The reason they are produced is, plantri produces simple graphs and the 2-connected duals are sometimes multi-edge non-simple (the multi-edges are not adjacent in the edge adjacency cyclic order around a given vertex) and as multi-edge graphs, they get excluded from the count and output for simple graphs. These graphs are also excluded from perfect compound square tiling processing as multi-edge graphs always produce imperfect tilings (multi-edges have the same currents in the electrical resistor graph and produce square tiling elements the same size). The exception to this rule is if one of the multi-edges (or equivalently, one of its dual edges) is the battery edge, then a perfect tiling can result. This is the case for compound squared rectangles, but not compound squared squares. In its simplest form, the perfect compound squared rectangles produced from these graphs have a square with its height equal to the squared rectangle height, these are called 'trivial' CPSRs. In higher orders the full height square can also be 'sandwiched' between two or more squared rectangles.

In summary, for square tilings of all kinds, the number of graphs to process is always less than the total for a complete edge class, as a graph class (v,f,e) and its dual class (f,v,e) produce the same tilings. The only difference being the tiles are rotated 90 degrees, and the dual class may include additional tilings from multi-edge duals in the case of 2-connected graphs.

The classes in the table below, outlined in black are self-dual, they are the largest vertex-edge class of each tiling order and need to be processed for compound tilings.

The requirement for minimum degree 3 graphs is needed to filter out graphs that always produce imperfect solutions, because degree 2 vertices in an electrical resistor (all resistors 1 Ohm) network-graph produce the same current on entry and exit to the vertex, creating 2 adjacent imperfect squares the same size in the tiling. Note that the minimum 2-connected simple, minimum degree 3 planar maps share the same graph classes (v,f,e) as the 3-connected planar maps with the exception of the triangulations, which are exclusively 3-connected graph classes.

These exactly 2-connected, minimum degree 3, simple planar map classes (v,f,e)> were processed to produce Compound Perfect Squared Squares (CPSSs) up to Order 32.

This method, developed by Stuart Anderson, and recently extended by Lorenz Milla was used successfully used to produce all perfect compound squared squares (CPSSs) from order 24 to 32. A similar method for enumerating compounds (CPSSs and CPSRs) was developed by Ian Gambini in his thesis in 1999 to produce perfect squares to order 26. One produces all the simple planar map classes (v,f,e) where v ≤ f of 2-connected minimum degree 3 planar graph embeddings for a given number of edges, these graphs can then be treated as electrical resistor networks. Solving the Kirchhoff equations for the network, produces node voltages and edge currents, which give the dissections of squared rectangles and squared squares. This process, like Duijvestijn's method for simple perfect squared squares, and like Gambini's graph methods, finds all compound perfect squares of a given order. The graphs can be generated and output by plantri. Plantri produces all the multiple planar embeddings of a 2-connected graph, in the case of the graph of a compound perfect square, these graph embeddings correspond to the isomers of the compound square.

The squared squares are encoded using Bouwkampcode or tablecode.

Updated on ... September 17th, 2018