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 recently (February 2013) written a paper 'Compound Perfect Squared Squares of the Order Twenties'. It is available from the Arxiv link. It gives some technical detail not found on the website. The website complements the paper in many ways, especially in providing a great many more dissection codes and illustrations, mainly because the website is not limited to the low-orders.

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, 20, 32, 48, 56, 64, 68, 72, 128, 132, 144, 192, 196, 256, 384, 512, 768, 1024, 1536, 2048. 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.

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 36 are now complete (subject to confirmation * ).

* Proof of completeness for CPSS orders 33 to 36 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) where f ≥ v were processed to produce Compound Perfect Squared Squares (CPSSs) up to Order 32.
Face Count in row and Vertex / Node Count in column
4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 0
5 0
6 1 1 1
7 1 3 8 5 3
8 7 35 72 86 45 18
9 2 60 307 776 1 041 827 340 81
10 47 647 3 395 9 091 14 407 13 929 8 340 2 775 490
11 12 652 7 647 38 876 111 076 196 733 227 109 171 280 82 480 22 938
12 325 9 582 94 278 468 211 1 392 870 2 705 083 3 569 351 3 245 692 2 008 337
13 59 6 654 136 628 1 192 511 5 787 837 17 809 062 37 202 518 54 742 447 57 610 106
14 2 442 121 204 1 937 266 15 371 597 73 232 219 231 418 254 513 465 002 826 127 629
15 368 64 232 2 049 784 27 294 367 201 223 550 944 081 828 3 050 583 419 7 118 588 029
16 18 916 1 409 199 33 135 263 384 201 336 2 670 262 417 12 372 474 462 40 737 789 123
17 2 363 607 746 27 605 162 520 501 148 5 415 258 877 35 873 044 824 164 504 197 269
18 150 161 15 550 020 504 051 385 8 029 314 932 76 560 153 685 487 357 085 282
19 16 253 5 669 267 346 878 657 8 781 416 772 122 444 980 192 1 086 695 466 605
20 1 211 635 165 904 623 7 078 135 680 148 139 089 112 1 853 914 453 287
21 115 434 52 506 185 4 155 483 256 135 838 928 647 2 442 907 887 833
22 9 907 524 1 729 724 802 93 851 956 346 2 495 065 189 852
23 845 452 484 275 815 48 097 147 678 1 970 430 918 021
24 81 906 985 17 741 744 390 1 192 135 393 463
25 6 332 201 4 457 530 966 542 507 190 519
26 683 630 684 179 802 186 339
27 48 345 998 40 995 197 547
28 5 753 913 598
29 375 071 543
Total (column) graphs 0 0 2 13 163 2 067 30 953 486 674 7 957 459 133 344 454 2 280 001 754 39 648 557 743 699 731 146 514 12 511 186 297 320
The column node graph total is OEIS sequence A187927.
The edge graph total is OEIS sequence A187928.
The number of edges is the sum of the row and columns indices minus 2 (Euler's Polyhedral formula; v + f = e + 2).     Stuart E. Anderson  &  Lorenz Milla 2011-2013  
edgesTotal 2-connected
planar min degree 3
maps by edge;
Total graphs to process
to enumerate all CPSSs
of order = edges-1:
order
10119
111110
124311
1315712
14423713
151356014
1644035415
171 48065916
185 1064 04717
1917 8907 97218
2063 26448 51719
21226 018100 93220
22812 354607 28121
232 936 8371 314 08322
2410 666 1887 789 33523
2538 901 19017 440 29724
26142 386 358101 938 14825
27~234 966 55926
28~1 356 038 48727
29~3 206 329 83828
30~18 297 453 99129
31~44 250 450 04830
32~250 011 787 78331
33~616 932 707 33932

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 ... May 3rd, 2014