Home‎ > ‎programming‎ > ‎Number Curios‎ > ‎

Simple Perfect Squared Rectangles


Introduction

I first got interested in simple perfect squared rectangles after reading a problem posted at the prime puzzle web-site. What's neat about this problem is that tiling a rectangle with squares (a problem with geometric constraints), also is a problem of arithmetic (adding squares of numbers).

The problem title has a very specific meaning:
simple - no sub-blocks that form rectangles
perfect - each square that is used in the tiling is used just once
squared - the rectangle is covered by non-overlapping squares


Here's an example of a 32x33 rectangle:

The picture above says that the 32x33 rectangle is tiled by 9 squares, 1x1, 4x4, 7x7, 8x8, 9x9, 10x10, 14x14, 15x15, 18x18.  It also says that
32x33 = 1056
= 1^2 + 4^2 + 7^2 + 8^2 + 9^2 + 10^2 + 14^2 + 15^2 + 18^2
= 1 + 16 + 49 + 64 + 81 + 100 + 196 + 225 + 324
= 1056



Here's an example of a 47x65 rectangle

The picture above says that the 47x65 rectangle is tiled by 10 squares, 3x3, 5x5, 6x6, 11x11, 17x17, 19x19, 22x22, 23x23, 24x24, 25x25.  It also says that
47x65 = 3055
= 3^2 + 5^2 + 6^2 + 11^2 + 17^2 + 19^2 + 22^2 + 23^2 + 24^2 + 25^2
= 9 + 25 + 36 + 121 + 289 + 361 + 484 + 529 + 576 + 625
= 3055



Bouwkamp Codes

Bouwkamp codes are an easy way to describe the dissection of the rectangle into square tiles.  The first set in parenthesis corresponds to the first row in the rectangle.  The set in the next parenthesis contain squares that fit in the first available row/column, where they all fit on the same row.

For example, consider the 32x33 rectangle, which has 4 dissections,
  • "(9, 10, 14) (8, 1) (7, 4) (18) (15)"
  • "(14, 10, 9) (1, 8) (4, 7) (18) (15)"
  • "(15, 18) (8, 7) (4, 14) (1, 10) (9)"
  • "(18, 15) (7, 8) (14, 4) (10, 1) (9)"
The first two are left-right reflections of each other, the last two are left-right reflections of each other, but they are also top-bottom reflections of the first two.

The first dissection was shown above, here are the remaining three.  They are nice to see as they illustrate the symmetry in the problem.  Note how even though the first configuration and the second both end in (18) (15), that the actual decomposition shows that they are positioned opposite to each other (the square of size 18 is on the right in the picture above, and it is on the left in the picture below).






Algorithm

The program has a simple 2-d array of integers, that was allocated/free'd for each array size.  A recursive algorithm was used to place squares of size 1x1 to size nxn, in position (0,0).  It then calls itself to find the first available row/column, and select a square, different from the first.

This procedure is subject to an explosive increase in the amount of work that needs to be done.  If you have 5 squares to try, and all 5 fit into the box, then there are 5! = 120 possible configurations of distinct tiles.  To see that, consider the following set of 5 squares, and the placement within a (linear) box.

---    ---   ---   ---   ---
 1      2     3     4     5
Position 1 could receive 5 possible squares (1x1, 2x2, ..., 5x5), position 2 could accept any of the remaining 4 squares, position 3 could accept the remaining 3 squares, position 4 has 2 possibilities, and position 5 has just 1 left (after all the other squares have been placed).

Now, consider the 32x33 rectangle which fits 9 squares.  There are 32 possible square tiles, (1x1, ..., 32x32), and I need to choose 9 of them to see of they fit into the 32x33 rectangle.  The number of ways to choose 9 square tiles from 32 is C(32, 9) = 32!/(23! x 9!) = 28,048,800, which can be done in a few seconds.

For the 47x65 rectangle, which fits 10 squares,the number of ways to choose 10 square tiles from 47 is C(47, 10) = 47! / (37! x 10!) = 5,178,066,751, which took over 2 hours.

Not mentioned was the fact that I don't know that there are only 9 square tiles that can fit in a 32x33 rectangle, (there could be 8 or 10), nor do I know if there are only 10 square tiles that fit in a 47x65 rectangle.



Additional Resources


Perfect Square Dissection - great introduction to simple perfect squared dissection at Mathworld
Squaring.net - website devoted to tilings by squares and triangles.
Squaring the Square - a nice article which shows how to use electrical networks to find simple perfect squared rectangles.
Electronic Computation of Squared Rectangles - A. J. W. Duijvestijn (thesis), a very well written explanation of using planar electrical networks to speed up the computation.


last updated July 27, 2011

Comments