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. 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 (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 been created using methods called 'transforms'. There are hundreds of transforms. A transform will often change one square tiling into another. One method is 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.
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. 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 29 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.
- plantri -pc2m3xuv n to count graphs where n is the number of vertices/nodes,
- plantri -pc2m3e#xuv n to count graphs by node and edge where # is edges
- plantri -pc2m3e$:#xuv n to count graphs by node and edge range where $ is lower edge bound, # upper edge bound
- plantri -pc2m3xv n filename, to count and generate graphs by node and save to file
- plantri -pc2m3e#xv n filename to count and generate graphs by node and edge and save to file
- plantri -pc2m3e$:#xv n filename to count and generate graphs by node and edge range and save to file
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). If required for another purpose multi-edge graphs, where f > v, can be generated by including the -d switch on the dual class (f < v).
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 imperfect tilings from the tilings i.e. 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.
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
This method recently developed by Stuart Anderson was used successfully used to produce all perfect compound squared squares (CPSSs) from order 24 to 28. A similar method for enumerating compounds (CPSSs and CPSRs) was developed by Ian Gambini in his thesis in 1999. 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.
Every CPSS is one of at least 4 isomers (tilings with the same set of tiles). 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 few numbers of isomers of which we have examples are 4, 8, 16, 32, 48 and 64.
- 1902 H.E. Dudeney published a puzzle called Lady Isabel's Casket that concerns the dissection of a square into different sized squares and a rectangle. According to David Singmaster 'Lady Isabel's Casket' appeared first in Strand Mag. 7 (Jan 1902) 584 and is the first published reference dealing with the dissection of a square into smaller different sized squares. It was also published in The Canterbury Puzzles in 1907.
- 1907-1914 S. Loyd published The Patch Quilt Puzzle. A square quilt made of 169 square patches of the same size is to be divided into the smallest number of square pieces by cutting along lattice lines. The answer, which is unique, is composed of 11 squares with sides 1,1,2,2,2,3,3,4,6,6,7 within a square of 13. It is neither perfect nor simple. Gardner states that this problem first appeared in 1907 in a puzzle magazine edited by Sam Loyd. David Singmaster lists it as first appearing in 1914 in Cyclopedia by Loyd but credits Loyd with publishing Our Puzzle Magazine in 1907 - 08. This puzzle also appeared in a publication by Henry Dudeney as Mrs Perkins Quilt. Problem 173 in Amusements in Mathematics. 1917
- 1938 R.P. Sprague found a solution to the problem of squaring the square. Sprague constructed his perfect solution using several copies of various sizes of Z. Moroń's Rectangle I (33x32), Rectangle II (65x47) and a third 12 order simple perfect rectangle and five other elemental squares to create an order 55, compound perfect squared square (CPSS) with side 4205.
- 1940 R.L. Brooks, C.A.B. Smith, A.H. Stone and W.T.Tutte published 'The Dissection of Rectangles into Squares" (1st page only), referring to an empirically constructed order 26 CPSS, side 608, attributed to Tutte. In the same year A.H. Stone uses 2 order 13 SPSRs as R1, R2 to construct and publish a Moroń dissection CPSS of order 28, side 1015.
- 1948 T.H.Willcocks, discovered a CPSS side 175, of order 24. It is one of 4 isomers (squarings with the same elements), since the subrectangle has 4 possible orientations.
- 1964 P.J. Federico constructed a CPSS with side 235 of order 25.
- 1964 Ludovit Vittek from Bratislava, Czech Republic published a CPSS in the Mathematica Slovaca, Vol. 14 (1964), No. 3, 234--235. This is same order 25 CPSS, side 235 which Federico is credited with discovering in 1964.
- 1965-66 E. Lainez constructed 2 CPSSs with sides 360, 460 of orders 26 and 27 respectively.
- 1972 N.D. Kazarinoff and R. Weitzenkamp proved the non-existence of a CPSS of order less than 22.
- 1978 P.J. Federico found the other CPSS (side 344) of order 25.
- 1982 A. J. W. Duijvestijn, P. J. Federico, P. Leeuw established the lower limit of the order of CPSSs and searched to find all that can exist up to and including order 24. The main results were; There are no CPSSs below order 24. and there is one and only one (THW 24:175) CPSS of order 24.
- 1980 -1999 Willcocks, Federico, Muller, Skinner, Morley and Bouwkamp continue to discover new CPSS transforms and steadily add more CPSS discoveries to Orders 26, 27, 28, 29 and above.
- 1999 I. Gambini published his doctoral thesis 'Quant aux carrés carrelés' on squared squares. He found the known CPSSs (and SPSS) up to and including order 26. He also published a table of CPSR ( and SPSR) counts up to and including order 24. For order 26 he identified 100 CPSS isomers which is correct, 92 isomers were known before Gambini, the additional square which completes the order (with side 512) has 8 isomers. However Gambini did not mention this CPSS in his thesis. This CPSS was evidently 'rediscovered' in 2010 by Anderson and Pegg.
- 2010 S.E. Anderson and Ed Pegg Jr. enumerate all CPSSs up to order 28. In January 2012 some errors were found in records of order 28 compounds isomers. A recount established a bijection between isomers and the graphs extracted in earlier processing, the original counts (Order 28; 143 CPSS , 948 isomers were confirmed). In isomer classes of CPSS, orders 24 to 28, the final counts are;
- 1 CPSS of order 24, with 4 isomers, (24:175 THW)
- 2 CPSSs of order 25, with 12 isomers, (25:235 PJF (4) & 25:344 PJF (8))
- 16 CPSSs of order 26, with 100 isomers, including 1 CPSS, 8 isomers, with side 512 not previously known, (except possibly to Ian Gambini) which completes this order.
- 46 CPSSs of order 27, with 220 isomers, including 7 CPSSs not previously known (with sides 345, 624, 648, 804, 820, 824, 857) which completes this order.
- 143 CPSSs of order 28, with 948 isomers, including 50 CPSSs not previously known, which completes this order.
- 2011 S.E. Anderson and Stephen Johnson commenced order 29 CPSSs, and processed all 2-connected min degree 3 graphs with up to 15 vertices. This leaves the largest graph class, the 16 vertex class, still to be processed.
- 2012 January, Geoffrey Morley discovers over 100 new CPSSs in orders 31, 32, 33 and 34.
CPSSs counts by order are listed in the OEIS as sequence A181340, Number of compound perfect squared squares of order n .
The people listed below have published or have been credited with the discovery of compound squared squares.
- AHS - Arthur H. Stone (United States, 1916-2000);
- AJD - A.J.W.D. (Arie) Duijvestijn (Netherlands, 1927-1998);
- A&P - Stuart E. Anderson (Australia) & Ed Pegg Jr (United States);
- C_M - Carsten Müller (Germany);
- CJB - Christoffel J. (Chris) Bouwkamp (Netherlands, 1916-2003);
- E_L - Enriquee Lainez (Spain);
- F&S - P.J. Federico & R.P. Sprague (PJF constructed 23 CPSSs of order 54 based on RPS's order 55 CPSS);
- GHM - Geoffrey H. Morley (England);
- I_G - Ian Gambini (France);
- JDS - Jasper D. Skinner II (United States);
- PJF - Pasquale J. Federico (United States, 1902-1982);
- RLB - R. Leonard Brooks (England, 1916-1993);
- RPS - Roland P. Sprague (Germany, 1894-1967);
- S_J - Stephen Johnson (United States);
- THW - T.H. (Phil) Willcocks (England);
- TTF - The Trinity Four (R.L. Brooks, C.A.B. Smith, A.H. Stone, W.T. Tutte);
- WTT - William T. (Bill) Tutte (Canada, 1917-2002).
- UNK - Unknown.
