The systematic development of the subject, using all the pieces from 1 to 6 squares, began in The Problemist Fairy Chess Supplement in December 1934, and continued in the Fairy Chess Review during the years 1936 to 1957. This was under the editorship of T. R. Dawson until his death in 1951 after which the "Dissections" column was run by Walter Stead. The dissection problems in FCR were not, except on two occasions, shown in diagram form due to the cost of making blocks for printing by the letterpress method then in use. Instead an ingenious method of coding was used, but this is now largely of historical interest only so will not be detailed here (full details were given in Chessics, vol.2, issue 28, 1986, pp.142-3).
The more squares in the polyominoes the more a systematic method is needed to enumerate them. The method adopted by Dr John Niemann (FCR June 1938) in his successful enumeration of the 8 and 9 square pieces was to group them first according to the dimensions of the smallest rectangle from which they can be cut. When the rectangle is non-square I take the standard orientation to be with the longer side horizontal. Here are the polyominoes of 1 to 4 squares arranged by this method.
An interesting domino question is: How many ways are there of covering a rectangular array of m×n squares with two-square pieces (dominoes). In Chessics [vol.2, issue 28, 1986, p.138] I gave this recurrence relation for the number:
T(m,n) = S(s\1...n)V(m,s)T(m,n–s)
where V(m,s) is the number of m×s dissections without a vertical fault line (i.e. a straight line of domino edges, dividing the rectangle from top to bottom, into two rectangles) and taking T(m,0) = 1. This method is practical for calculating the totals when m < 4 since the values of V(m,s) are then easily found by direct construction, mostly being zero. The nonzero cases are: V(1,2) = 1, V(2,1) = 1, V(2,2) = 1, V(3,2) = 3, V(3,2h) = 2, V(4,1) = 1, V(4,2) = 4, V(4,2h–1) = 2, V(4,2h) = 3, with h > 1. The problem remains of calculating V(m,n) for larger values and also of determining the number F(m,n) of fault-free dissections (with neither vertical nor horizontal fault lines).
W.L.Patton had shown in American Mathematical Monthly 1961 that the 2×n case is solved by the Fibonacci sequence given by the recurrence: T(2,n) = T(2,n–1) + T(2,n–2). Chris Holt in Mathematical Spectrum 1994/5 (vol.27, No.3, p.62) gave a recurrence for the 3×2k case: T(3,2k) = 4T(3,2k–2) – T(3,2k–4). In the same journal 1995/6 (vol.29, No.2, p.44) I supplied a recurrence for the 4×n case: T(4,n) = T(4,n–1) + 5T(4,n–2) + T(4,n–3) – T(4,n–4). This gives the total of 36 arrangements on the 4×4 board and 2245 domino dissections of the half-chessboard 4×8. These formulas are particular cases of the above more general recurrence.
I learnt in 1996 that a formula solving the general problem was given by P.W.Kasteleyn in 1961 ["The statistics of dimers on a lattice, Part I" Physica, vol.27, pp.1209-25], but it surprisingly uses serial multiplication instead of addition, and involves cosine functions and fourth roots, so I don't consider it to be "recreational" mathematics. James Propp (Massachusetts Institute of Technology), using Kasteleyn's results, calculated the number of domino tilings of the 6×6 board as 6728 = 2×58² and of the 8×8 chessboard to be 12,988,816 = 3604². [For the formula and a table of all results up to 72 cells, calculated by Robin J. Chapman (University of Exeter) see The Games and Puzzles Journal No.14, 1996 pp.204-5.]
There are five distinct 4-square shapes, as shown above. Here is a result on tetrominoes: There are 117 ways of dissecting a 4×4 board into 4 pieces, each of 4 squares. There are 22 geometrically distinct solutions (i.e. not counting rotations and reflections as different). [B. Larsson FCR April 1937] A dissection with all four shapes different is impossible. The numbers indicate the symmetry of the pattern, i.e. the number of different appearances it can have by rotation or reflection; thus 8 indicates asymmetry, 4 binary symmetry (by reflection or rotation), 2 quaternary symmetry (by reflection or rotation) and 1 octonary (perfect square) symmetry.
| 1 | 2 | ||||||||||||||||||||||||||||||||||
| 4 | |||||||||||||||||||||||||||||||||||
| 8 | |||||||||||||||||||||||||||||||||||
There are 12 distinct 5-square pieces:
The best-known puzzle with the 12 differently shaped 5-square pieces is to cover a chessboard with them, leaving the four uncovered squares in various specified positions. T. R. Dawson [FCR April 1937] gave three arrangements that prove that the four squares can be left in 2×2 formation anywhere on the board (10 geometrically distinct position). The L-shaped piece bordering two sides of the 2×2 in Dawson's arrangements can be rotated within the 3×3 area it occupies, to provide other positions for the 2×2.
|
|
|
|
Computer analysis by D. S. Scott in 1958 (reported in Golomb's book) counted 65 geometrically different solutions with the 2×2 in the centre.
Another solution by Dawson [FCR June/August 1938] shows a 2×2 space with all the 5-square pieces abutting the edges of the board. Try this as an exercise.
The 6-square pieces (hexominoes) were first enumerated by H. D. Benjamin in the Problemist Fairy Chess Supplement December 1934. There are 35 of them in all.
Kadner's Theorem. It is impossible to use the 35 hexominoes to cover any rectangle. This was first proved by Dr F. Kadner (PFCS February 1935 p.105). The reason is that, if the pieces are placed on a chequered board then 24 of them will each cover 3 black and 3 white squares, but 11 of them will cover 2 of one colour and 4 of the other. It follows that any chequered area covered by the 35 pieces must show a colour difference (c.d.) of 2, 6, 10, 14, 18 or 22 (i.e. an excess of squares of one colour over squares of the other colour). Any chequered rectangle 2n×m has n×m squares of each colour. (Since the total number of squares in the hexominoes is 210 = 2×3×5×7 the only rectangles that need be considered are 1×210, 2×105, 3×70, 5×42, 6×35, 7×30, 10×21, 14×15.)
The first published hexomino dissection was by H.D.Benjamin (FCR Feb/Apr 1937 prob.2622): Triangle with serrated hypotenuse. Side 20, c.d. = 10. Another early example was by F. Hansson (FCR Feb/Oct 1950 prob.8558): Square with rectangular hole. 15×15 – 3×5, c.d. = 2. In Chessics (vol.2, issue 28, 1986, pp.144-5) I gave examples illustrating the other c.d. values: Cross 19×19 – 4(6×6) with 7 small holes, c.d. = 6. Serrated square with diagonal 21 and 1×11 hole along a diagonal, c.d. = 22. Triangle with two serrated sides, Hypotenuse 29, with 3×5 hole, c.d. = 14. And the following "stepped lozenge with hole", c.d. = 18. I have coloured it using five colours each occurring seven times.
The sizes 1 to 6 probably provide enough possiblities to satisfy most people's interest in polyominoes, but for the real fanatic the next step must be to make a set of the 108 seven-square pieces. These were first counted by F. Douglas and W. E. Lester in FCR April 1937.
This diagram shows an arrangement of the heptominioes by Walter Stead, dated 26 August 1973 (in his notebooks, but possibly not published until I included it in Chessics vol.2, issue 28, 1986, p.147). In colouring it I have used six colours each occuring 18 times.
The first correct count of the 8-square pieces was by Dr John Niemann (FCR June 1938). Their total is 369.
The first correct count of the 9-square pieces was done by Dr Niemann at the same time as his count of the octominoes (FCR June 1938). Their total is 1285.
Niemann's count of the 10s (FCR Dec 1939) was one short and the correct figure of 4655 was not found until 1966 by T. R. Parkin (reported in the UK edition of Golomb's book).