This collection of SPSSs from Order 21 to 37 is a complete collection. The number of squared squares grows exponentially with the order. For SPSSs of order 38 and above we have a partial, incomplete collection.
This collection of simple squared squares has been assembled from many sources, with material from published and unpublished collections, mathematics journals, books, and recent computer searches. The catalogue is presented, arranged by order, beginning with the single simple perfect squared square of order 21. SPSSs are viewable in javascript and pdf. Other selections of this collection are available for download. For definitions of squared squares and squared rectangles, including 'simple', compound', 'perfect' and 'imperfect' see here.
The first appearance of a reference to this problem occurred in the early twentieth century. Ernest Dudeney was a writer who published mathematical puzzles in magazines. In 1907 he published The Canterbury Puzzles which contained a puzzle called Lady Isabel's Casket which concerns the dissection of a square into different sized squares and a rectangle. According to David Singmaster 'Lady Isabel's Casket' appeared first in The London Magazine 7 (Jan 1902) 584 and is the first published reference dealing with the dissection of a square into smaller different sized squares.
Max Dehn was the first mathematician to do work on the dissection of rectangles into squares. Dehn studied at Göttingen under Hilbert's supervision obtaining his doctorate in 1900. Max Dehn had studied the squaring problem in 1903 and proved;
A rectangle can be squared if and only if its sides are commensurable.
If a rectangle can be squared then there are infinitely many perfect squarings.
From 1921 until 1935 he held the chair of Pure and Applied Mathematics at the University of Frankfurt but he was forced to leave his post by the Nazi regime in 1938.
Samuel Loyd was the creator of many famous mathematical puzzles and recreations. Loyd produced over 10,000 puzzles in his lifetime many involving sophisticated mathematical ideas. In 1914 The Patch Quilt Puzzle appeared in Sam Loyd's “Cyclopedia of Puzzles”, in it, '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'. 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.
In 1925 Zbigniew Moroń published a paper, 'O Rozkladach Prostokatow Na Kwadraty' (On the Dissection of a Rectangle into Squares). Moroń gave the first examples of rectangles divided into unequal squares in his paper. He doesn't indicate how they were obtained. Rectangle I is 33 x 32 in size and is divided into 9 unequal squares. Rectangle II is 65 x 47 and has ten squares. According to correspondence quoted by P J Federico, Prof Wladyslaw Orlicz wrote of Moroń in a letter to Dr. Stanislaw Dobrzycki of Lubin, Poland;
“Zbigniew Moroń was my younger schoolmate when studying mathematics at the University of Lwów; about 1923-24 we were both junior assistants in the Institute of Mathematics. Professor Stanislaw Ruziewicz (who was then professor of mathematics at the University) communicated to us the problem of the dissection of a rectangle into squares. He had heard of it from the mathematicians of the University of Krakow who took interest in it. As young men we enthusiastically engaged ourselves in investigating this problem, but after some time we all came to the conclusion that it was certainly as difficult as many other apparently simple questions in number theory. The examples found by Moroń were to us a great surprise. Before the World War II Moroń was a teacher in secondary schools; after it he was too, and dwelt in Wraclow, where he died some 5 years ago.”
Further, in a translation of a later paper by Zbigniew Moroń, by Dr Dobrzycki, Zbigniew Moroń states,
"In the years 1925-28 I found further results in this domain; among others I proved that it is impossible to construct a rectangle with less than 9 different squares; I also knew of the dissection of a square which was later given by Sprague. Nevertheless I did not publish them, but only exposed them at meetings of the mathematical seminar of Professor Ruziewicz."
It is possible that Zbigniew Moroń discovered Sprague's square more than 10 years before Sprague himself, as the Sprague square is partly composed of the Moroń Rectangles I and II, but no other evidence has emerged to support the claim.
In the 1930s the problem "can one decompose a square into a finite number of squares all different?" was added to the Scottish Book as problem 59 by Professor Ruziewicz. The Scottish Book was named after the Scottish Cafe - which was in Lwów Poland (now Lviv, Ukraine),- where Lwów mathematicians would converse and work on math problems, recording them in the Scottish Book . No solution was found to problem 59. Professor Stanislaw Ruziewicz, along with other Lwów mathematicians and academics were murdered by the Nazis and their collaborators in 1942.
In 1930 Michio Abe, published a paper "Covering the square by squares without overlapping," in the Journal of Japan Mathematical Physics. Three things have been said about Abe's work; Working in apparent isolation, he produced over 600 simple perfect rectangles. It appears he was aware of the literature of his day, in particular Z Moron´. He was far ahead of the Germans in researching the topic. Abe published a second paper in 1931. An English translation was published in 1932. This was his last known paper, in it he showed that an infinite series of compound perfect rectangles can be built up (from a simple perfect rectangle [191 x 195]) whose size-ratios approach the limit of one. Abe noted that the problem of squaring the square has not yet been solved.
Tutte wrote in the 1950s, "In 1936 there were a few references in the literature to the problem of cutting up a rectangle into unequal squares. Thus it was known that a rectangle of sides 32 and 33 can be dissected into nine squares with sides of 1,4,7,8,9,10,14,15, and 18 units. Stone was intrigued by a statement in Dudeney's Canterbury Puzzles which seemed to imply that is is impossible to cut up a square into unequal smaller squares. He tried to prove the impossibility for himself, but without success." R.L. Brooks, C.A.B. Smith, A.H. Stone and W.T.Tutte then teamed up to work on the problem. In 1990 Cedric A. B. Smith wrote in personal communication to J.D. Skinner, "W. R. Dean (later Professor of Applied Mathematics at University College, London) is largely responsible for the development of the idea of squaring the square. Dean visited Arthur Stone's school before Arthur came to Cambridge and said that an unsolved problem was to show that a square cannot be dissected into a finite number of unequal squares". This was at or prior to 1935. In 1997 Cedric A. B. Smith wrote a paper; 'Did Erdös save western civilization?'. In an anecdotal manner the author describes how he became acquainted in the 1930s with a geometric conjecture by Paul Erdös, on the dissection of a square into a finite number of smaller squares. Erdös conjectured such a dissection must contain a least two squares the same size. There was a related conjecture known as Lusin's conjecture. In 1930 Kraitchik published personal communication from Russian mathematician N. N. Lusin that is was impossible to dissect a square into a finite number of dfferent elements. Perhaps Lusin was the originator of the conjecture, perhaps Erdös heard of it from the Polish mathematicians, perhaps Professor Dean heard it from Erdös, in any case Erdös publicised the problem as he often transmitted mathematical ideas from place to place in his travels. As a student in Cambridge England, Smith was introduced to the problem by Arthur Stone. They jointly discussed with R. L. Brooks and then chemist William T. Tutte the relation of that conjecture to Kirchhoff's theory of electrical networks. They finally (1940) showed Erdös's conjecture to be incorrect. Tutte, later founding President of the Institute of Combinatorics and Its Applications, became involved into the work at Bletchley Park during World War II, where the German codes were broken, hastening the end of WWII and saving millions of lives. Since he had been drawn into mathematics by Erdös's conjecture the author is led to the provoking title of this paper. It should be noted the Official Secrets Act prevented any detailed discussion of Tutte's role or the contributions of others to breaking German codes.
- 1939 Announcement by C. A. B. Smith that Tutte had found a perfect squared square with no perfect subrectangle. Minutes of the 204th Meeting of the Trinity Mathematical Society (Cambridge) (24 Apr 1939). Minute Books, vol. III, p. 248. (Singmaster)
- 1939 R.P. Sprague published 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. The rest of this webpage deals specifically with Simple Perfect Squared Squares (SPSSs). Further details on Compound Perfect Squared Square (CPSS) discoveries, along with a detailed timeline are here.
- 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 order 55 SPSS, side 5468 using theoretical methods involving the use of symmetry in electrical networks, attributed to all four authors.
- 1945 Alan Turing completed writing a document named the "Proposed Electronic Calculator", later this was referred to as the ACE (Automatic Computing Engine) report. In this document Turing laid out his vision for what an electronic computer could achieve, and how it could work. To illustrate his ideas, he gave five examples of possible applications involving calculations of practical importance, which at the time required months or years of work on desk machines. But another four were non-numerical, one involved modelling electrical circuits and calculating the response to given input signals, another non-numerical problem was described thus "A jig-saw puzzle is made up by cutting up a halma-board into pieces each consisting of a number of whole squares. The calculator could be made to find a solution of the jig-saw, and, if they were not too numerous, to list all solutions. " In Alan Turing: The Enigma, by Andrew Hodges (the film The Imitation Game, starring Benedict Cumberbatch is loosely based on this book) the author notes (p417) that W. T. Tutte had worked on this pure-mathematical problem. So now we know that Bill Tutte and Alan Turing must have discussed the problem of the Squared Square, presumably while they both worked at Bletchley Park, and as both men were pioneers in the development and application of computing machinery and mathematical analysis and algorithms to cryptoanalysis, it seems they must have given careful consideration to using computers (which had only just come into existence) to solve this problem. All this nearly two decades before Bouwkamp and Duijvestijn used a computer to attack the problem in the early 1960s.
- 1946-7 C.J. Bouwkamp, published 'On the dissection of rectangles into squares', 'Paper I', 'Papers II and Paper III' and 'On the construction of simple perfect squared squares' (Koninkl. Nederl. Akad. Wetensch. Proc. Ser. A)
- 1950 R.L. Brooks discovery of a simple perfect squared square (SPSS), side 4920 of order 38 was published by W.T. Tutte in 1950, in a paper which demonstrated some advanced mathematical techniques. A simple perfect squared square of the 52nd order, due to Tutte and Smith is given, as is one of 70th order and side 384948 and the 69th order with a side of 7919535. The paper was submitted 18 March 1948.
- 1959 The addendum (pp. 162-4) to Tutte's chapter in Martin Gardner's "More Mathematical Puzzles and Diversions" says "The smallest published square that is both simple and perfect is a 38th-order square with a side of 4,920, discovered by R.L. Brooks. In 1959 this was bettered by T.H. Willcocks of Bristol, with a 37th-order square, 1,947 on the side."
- 1962 A.J.W. Duijvestijn supervised by C.J. Bouwkamp, in his PhD thesis 'Electronic Computation Of Squared Rectangles', showed no SPSS exists with fewer than 20 squares.
- 1964 J.C. Wilson found an SPSS with side 503 of order 25.
- 1966 T.H. Willcocks constructed 2 SPSSs with sides 1415, 2606 of order 31.
- 1967 G.H. Morley's SPSS method published in Eureka. Six examples, from 59:2568805 to 60:5629849, have been be found. They include 60:616457A, wrongly stated in the article to have side 616,467. By modifications of his method Morley has also found SPSSs of orders 48 and 49.
- 1967 T.H. Willcocks constructs 2 SPSSs with sides 1360, 1372 of order 31.
- 1967 J.C. Wilson included in his PhD thesis 5 new SPSSs of order 25 (including the one he found in 1964) and 24 new SPSSs of order 26.
- 1969 T.H. Willcocks constructed an SPSS with side 900 of order 27.
- 1978 P.J. Federico found two SPSSs of order 25.
- 1978 Mar, A.J.W. Duijvestijn, SPSS order 21 enumerated; 1 SPSS (21 : 112 x 112) proved order minimal and unique.
- 1978 A.J. W. Duijvestijn found an SPSS side 110 of order 22. T.H. Willcocks was able to transform it into a different SPSS with side 110 of order 22. By Gambini's result these 2 and another 110 in order 23 are the smallest size perfect squared squares.
- 1990 J.D. Skinner constructed SPSSs of side 180 and side 188 of order 23.
- 1990 C.J. Bouwkamp constructed 2 SPSSs of order 24 of side 186 and side 288 of order 24.
- 1991 Jul, A.J.W. Duijvestijn enumerated the remaining SPSSs of orders 21 - 24.
- 1992 Jan, C.J. Bouwkamp constructed 5 SPSS of order 25 and 21 of order 26.
- 1992 A.J.W. Duijvestijn enumerated the remaining SPSSs of order 25 and published SPSSs of orders 21 to 25
- 1993 J.D. Skinner found 3 SPSSs of order 26.
- 1993 During the period of January 7, 1993 to March 15, 1993 A.J.W. Duijvestijn calculated the order-26 squared-square solutions by means of four HP workstations connected to the Eindhoven university network. Their speed was 75 Mflops. The machines were only available to him during the nights and the weekends. A.J.W. Duijvestijn published the results as Simple Perfect Squared Squares and 2 x 1 Squared Rectangles of Order 26 in 1996.
- 1999 I. Gambini published his doctoral thesis 'Quant aux carrés carrelés' on squared squares. He confirmed Duijvestijn's counts of SPSSs up to order 26. With a second algorithm a lot more efficient but incomplete he obtained more than 30,000 squared squares. He also published a paper
'A method for cutting squares into distinct squares'- 2003 J.D. Skinner completed enumeration of SPSSs of order 27. By 2003, Skinner had also enumerated 94% of order 28 and 45% of order 29 and about 22% (estimated) of order 30 SPSSs.
- 2003 S.E. Anderson, in a collaboration with J.D. Skinner in 2002-3, found 60 SPSSs of order 28
- 2007 G.H. Morley published 130 SPSSs of order 31.
- 2010 S.E. Anderson and Ed Pegg Jr. enumerate all SPSSs up to order 28, and begin investigation of order 29. They confirm that the known SPSSs up to order 27 are complete, and find the remaining 30 of a total 3001. SPSSs of order 28..
- 2011 August S.E. Anderson, and Stephen Johnson finalise SPSSs and SISSs of order 29. They find a total of 7901 SPSSs and 326042 SISSs in order 29.
- 2011 October, Stephen Johnson discovers 500+ SPSSs from order 30 to order 36.
- 2012 April Lorenz Milla found SPSSs of sides 1375 and 2704 in order 31. Also in April 2012, Lorenz Milla completed searches of the 13 and 14 vertex, 31 edge polyhedral graph classes, using Stuart Anderson's noddy (node analysis on electrical nets) software and found 61 new SPSS of order 30. He also found an additional 8 SPSS in order 31.
- 2013 January and February; James Williams wrote a program which he ran for 6 weeks which produced over 15 million SPSSs from orders 21 to 44. The software was not exhastive, it did not find all SPSSs in a given order, the goal was to find as many perfect squares as possible in a practical amount of time. No particular effort was made to search for a particular kind of square ( low order, etc. ) but rather just to find the most. His algorithm looks for squares for which the associated electrical network can be cut roughly in half by cutting at exactly three nodes. The resulting two halves are connected together in a squared square. A number of tests or 'filters' are used to evaluate whether a pair of networks will form a perfect square and these tests speed up the processing considerably. This collection, the 'Williams Collection', is currently being added to the site, beginning with order 30 (no new discoveries were found below order 30).
- 2013 March and April; Lorenz Milla and Stuart Anderson enumerated simple squared squares of order 30. Lorenz used plantri (McKay/Brinkmann) to generate graphs, and Stuart Anderson's sqfind to find squared squares and his sqt to encode the dissections. Lorenz ran the programs on 17 dual core computers over the Easter school holidays. Some 6756 new SPSSs were found, combined with the known 13810 SPSSs of order 30 (including 9189 SPSSs found in Jan/Feb 2013 by James Williams) there are 20566 order 30 SPSSs in total. Simple Imperfect Squared Squares (SISSs) of order 30 were also enumerated. The total for order 30 SISSs is 667403.
- 2013 May ; Lorenz Milla and Stuart Anderson enumerated compound perfect squared squares of order 30.
- 2013 June to September ; Lorenz Milla and Stuart Anderson rewrote Stuart's software to incorporate a determinant factorisation technique recommended by William Tutte in his writings to speed up squared square searches, this was used by Duijvestijn in his 1960 thesis. Lorenz replaced the Boost library with C arrays and handwritten linear algebra routines; LU decomposition was replaced with LDL decomposition (planar maps are symmetrical, so LDL Cholesky decomposition is possible and twice as fast as LU decomposition). Lorenz also wrote a plantri plugin to filter graphs using the determinant factorisation technique as they were produced, he was also able to speed up the routines in Stuart's sqfind and sqt programs and combine the plantri plugin and sqfind into a single program mandrill (a combination of the names Milla and Anderson). The end result was squared square software 35 times faster than what was used several months ago. This made it possible to complete the enumeration of order 31 and 32 compound perfect (CPSSs), simple perfect (SPSSs) and simple imperfect squared squares (SISSs) in under 2 months. The computations were done by Lorenz on his computers. There are 54541 SPSSs in order 31 and 144161 SPSSs in order 32. There are 1627218 SISSs in order 31 and 3508516 SISSs in order 32. The software was run for a second time in September by both Stuart and Lorenz due to a bug affecting a small number of determinant factorisation cases, CPSS and SPSS totals remained the same, but SISS totals were increased slightly.
- 2013 December ; Stephen Johnson collated the results of his squared square searches in early 2013 and made them available. A number of new SPSS discoveries in orders 33-37 were found, these have been included in the website.
- 2014 March ; Brian Trial uses a new 'Ell-Munch' method to find 114712 SPSSs in orders where there are large gaps in the current catalogues. By “ell,” we mean any six-sided figure whose sides are parallel to the coordinate axes (Henle 2008). Brian's lowest order find is of order 34 and the highest is order 236, with the majority of finds in the orders 30s to 70s. He wrote;
There are 4 different types of Ell depending on what quadrant the cut out section is located, which could have any rectangular shape, some quite stretched in one direction as we can see in the solutions so far. Another "munch" can be done along any one of the 6 sides of the Ell depending on the sides' relative sizes.- 2014 May June ; Jim Williams, with new software enumerated the SPSSs of order 33. In 2 weeks he found all 378197 SPSSs of this order.
- 2016 April ; Jim Williams, enumerated the SPSSs of order 34 and 35. He found 990981 SPSSs in order 34 and 2578081 SPSSs in order 35.
- 2018 Bernard Moss, using a transform technique, found many SPSSs in order 37 up to order 116. Many of these were transforms of Jim Williams 2013 & 2014 discoveries, and Brian Trial's 2014 discoveries.
- 2020 Bernard Moss, using more transform techniques, found another 58,000 SPSSs in orders 48 to 85, including some quite small SPSSs in those orders.
- 2020 July ; Jim Williams finalised the enumeration of order 36 and order 37 SPSSs. There are 6674067 SPSSs in order 36 and 17086918 in order 37 SPSSs.
- 2020 Bernard Moss using another transform technique, with assistance from Stuart Anderson, found over 2.3 million SPSS from order 48 to 85 (plus a few of higher orders) by amalgamating pairs of Jim Williams' 2013 & 2014 discoveries.
SPSS counts are listed at OEIS as the sequence;
A006983 Number of simple perfect squared squares of order n.
Using Brendan McKay and Gunnar Brinkmann's published data and plantri software, Stuart E Anderson updated Gérard P. Michon's original table of polyhedral graphs (also known as c-nets and 3-connected planar graphs). These are processed to produce simple, perfect and simple imperfect squared rectangles and squared squares. The number of graphs to process is less than the total for an edge class as edge classes have a dual class which produces the same tilings (the only difference being the tiles are rotated 90 degrees). Only graphs classes where v ≤ f need to be processed. The classes outlined in black are self-dual and are also processed.
These at least 3-connected, minimum degree 3, simple planar map classes (v,f,e) where f ≥ v were processed to produce Simple Perfect Squared Squares (SPSSs) up to Order 32.
|
|
- A&P - Stuart E. Anderson and Ed. Pegg Jnr
- AHS - Arthur H. Stone (1916-2000);
- AJD - A.J.W.D. (Arie) Duijvestijn (1927-1998);
- AJP - Stuart Anderson, Stephen Johnson, Ed Pegg Jnr
- A&M - Stuart Anderson and Lorenz Milla
- B_T - Brian Trial (1966-);
- BLM - Bernard L. Moss
- CJB - Christoffel J. (Chris) Bouwkamp (1916-2003);
- EPJ - Ed. Pegg Jnr (1963-);
- F&W - Pasquale J. Federico and T.H. (Phil) Willcocks
- GHM - Geoffrey H. Morley (1944-);
- I_G - Ian Gambini ;
- JBW - James B. Williams
- JCW - John C. Wilson
- JDS - Jasper D. Skinner II (1947-);
- L_M - Lorenz Milla ;
- M&A - Lorenz Milla & Stuart E. Anderson;
- PJF - Pasquale J. Federico (1902-1982);
- RLB - R. Leonard Brooks (1916-1993);
- SEA - Stuart E. Anderson (1959-)
- S_J - Stephen Johnson (1958-);
- THW - T.H. (Phil) Willcocks (1912-2004);
- WTT - William T. (Bill) Tutte (1917-2002);
The following publications have featured extensive collections of Simple Perfect Squared Squares;
Updated on ... Oct 23 2020