Tiling with Squares

A square or rectangle is said to be 'squared' into n squares if it is tiled into n squares of sizes s₁,s₂,s₃,..s_n. A rectangle can be squared if its sides are commensurable (in rational proportion, both being integral mutiples of the same quantity) The sizes of the squares s_i are shown as integers and the number of squares n is called the order.

Techniques for making square tilings

Creating Squared Rectangles from Electrical Networks

It was shown by Brooks, Smith, Stone and Tutte that simple squared rectangles correspond to 3-connected planar electrical networks with one edge removed and an electromotive force applied. They reinterpreted the problem as one of electrical circuits. Squares in a rectangle dissection were replaced by edges of unit resistance in an electrical network, connected as nodes at the top and bottom edges of the squares and the rectangle.

By making the correspondence between electrical networks and square dissections, it becomes possible by enumerating all electrical networks with a given number of edges, to produce all possible simple tilings of rectangles with a given number of squares.

3-connected planar graphs are equivalent to the '1-skeletons' (i.e. edges and vertices) of polyhedra, this is known as Steinitz's theorem. The problem of enumerating polyhedra is the same as enumerating 3-connected planar graphs. Tutte developed a theory for exhaustively creating 3-connected planar graphs (also called c-nets) using his Wheel Theorem and also developed enumeration formulae to estimate the numbers of c-nets by edge.

Duijvestijn and Bouwkamp created c-nets by computer using this theory. The method created many duplicate c-nets so a major computational effort went into eliminating them. Recently new techniques for producing c-nets have been developed, these include Brendan MacKay and Gunnar Brinkmann's plantri which generates exactly one member of each isomorphism class for many types of planar graph, and A Direct Decomposition of 3-Connected Planar Graphs by Bodirsky, Gropl, Johanssen, and Kang.

Once a supply of c-nets has been produced, each c-net with a selected edge is treated as an electrical network. The currents and voltages in the network branches correspond to the sizes of the squares and they can be calculated using Kirchhoff's Laws and the Matrix Tree Theorem. As the simple squared rectangles are produced, they can be searched for simple perfect squared squares.

Ian Gambini's Decomposition Approach

Ian Gambini in his thesis (French) has produced squared squares using 2 methods, his first method for a given integer n obtains every decomposition using n squares, the second method is a lot more efficient but incomplete and allows the calculation of decompositions of a square into distinct sized squares to generate squared squares, squared cylinders and tori. Gambini has claimed over 30,000 squared squares discovered with many in higher orders. Only a small selection of these are shown in his published work. It is not clear if all 30,000 are distinct tilings when rotations and reflections are eliminated.

Subdivision Tiling and Squared Rectangles

Cannon, Floyd and Parry use a coded tiling file and some simple finite subdivision rules with their program subdivide.c, to recursively subdivide a tiling into a complex subdivided tiling. Another program squarect.c, inputs the tiling file and outputs a postscript file for the associated squared rectangle. The order of these subdivided tilings increases exponentially with the number of sub-division levels. Subdivision creates imperfect and compound tilings. The squaring of the rectangle is done using the cyclic algorithm, as described in Squaring rectangles: the finite Riemann mapping theorem, by J.W. Cannon, W.J. Floyd, and W.R. Parry, Contemporary Mathematics, Volume 169, 1994.

---