ç Index to Chessboard Dissection Problems

# Enumeration and Listing of N-Square Pieces

The square-pieces of up to six squares were first listed in the variant chess magazine Fairy Chess Review (Volume 3, Issue 5, April 1937 pages 46-7) in "A Notation for Dissection Problems" by T. R. Dawson and W. E. Lester. They wrote: "It may be noted that the numbering and orientation has been done on systematic lines as follows. The pieces are ranged in increasing size. Where they are of the same size the number of files increases from left to right, while squares on second and later files move successively lower." These rules however are not sufficient to fix the list exactly (both in the sequence and orientation of the pieces), and I am not clear if additional unstated rules were in operation or whether an arbitrary element was involved. For details of the FCR numbering scheme see: Key to FCR Notation

## The Binary Number Method

However, a fully systematic listing is indeed possible. This can be done by interpreting each n-square piece as a binary number. To do this we imagine an array of 0s in rows of n. Then we represent the n-square shape as an array of 1s, replacing some of these 0s, and arranged to give the smallest possible binary number when read from the top left row by row. This principally means that the first 1 should be as low as possible and as far to the right as possible (so that the first power of 2 in the sum of binary terms is as low as possible).

For instance the first asymmetric omino, the L-shaped 4-square piece, can occur in eight different orientations, and these can be interpreted as binary numbers as shown here where the eight orientations are arranged in increasing sequence of the number represented. The numbers below the binary arrays show the decimal equivalents of the binary numbers. 0000 0000 0000 0000 0001 0010 0011 0011 0001 0100 0111 0111 0001 0010 0001 0010 0111 0111 0001 0100 0011 0011 0001 0010 = 23 = 71 = 113 = 116 = 275 = 547 = 785 = 802

For each value of n, the numbers defined by this method are in order of magnitude, and no two can be equal, so they provide an exact sequencing and orientation of the ominoes.

## The Pieces of 1 to 5 Squares

By this binary number method the pieces from 1 to 5 squares are represented as: I choose to letter (or number) the sets and number the ominoes within each set, whereas in FCR the whole sequence was numbered 1 to 21. This sequence agrees with that given by Dawson and Lester except for transposition of the -pieces 5 (15) and 6 (14). The relative orientations also agree except in the cases of the -piece 5 (9), and the -pieces 5 (15), 8 (17), 10 (19) and 11 (20).

## The Pieces of 6 Squares

The 6-square pieces were first enumerated by H. D. Benjamin in Problemist Fairy Chess Supplement, December 1934. Here is the listing of the 35 pieces by the binary number method: I number this set 1 to 35. (Dawson and Lester used 22 to 56 but their sequence departs considerably from the binary number method.)

## The Pieces of 7 Squares

The 108 pieces of 7 squares were first counted by F. Douglas and W. E. Lester in FCR April 1937. A listing of the pieces was made by Frans Hansson in 1938, following a similar scheme to that used in FCR for the pieces 1 to 6, however no 7-square piece dissections were published in FCR, so the numbering was not used. Here is my listing by the binary number method: ## The Pieces of 8 to 10 Squares

The first correct counts of the 8 and 9 square pieces were done by Dr J. Niemann (FCR June 1938), his count of the 10s however (FCR December 1939) was one short and the correct figure was nor found until 1966 by T. R. Parkin (reported in the UK edition of Golomb's book, Polyominoes). Niemann's method of counting the pieces was to group them according to the dimensions of the smallest rectangle from which they can be cut.

This table shows the numbers of square-pieces of all sizes up to 10 classified by outline rectangle.

 n 1 2 3 4 5 6 7 8 9 10 1×n 1 1 1 1 1 1 1 1 1 1 2×2 1 1 2×3 3 2 1 2×4 3 6 2 1 2×5 5 11 10 3 1 2×6 5 19 22 15 2×7 7 28 52 2×8 7 40 2×9 9 3×3 6 7 7 3 1 3×4 15 39 59 42 21 3×5 25 96 210 255 3×6 35 188 550 3×7 49 332 3×8 63 4×4 18 77 181 266 4×5 61 383 1304 4×6 97 822 4×7 155 5×5 73 529 5×6 240 Total 1 1 2 5 12 35 108 369 1285 4655

The count of the 4×4 ten-pieces is a particularly difficult and interesting enumeration. For Chessics #28 I checked the count by dividing the 4×4 into its 2×2 quarters and classifying the pieces by the ways in which the 6 squares that are cut away are distributed among the quarters. There are 13 cases, as shown in the chart below, with the number of pieces of each type and the number of symmetric pieces of each type, given below each case-diagram.

 4 2 0 0
 4 0 0 2
 4 1 0 1
 4 1 1 0
 3 3 0 0
 3 0 0 3
 3 2 0 1
 3 2 1 0
 3 1 0 2
 3 1 1 1
 2 2 2 0
 2 2 1 1
 2 1 1 2
totals
2 1 14 10 0 2 16 17 26 63 11 65 39 266
0 0 0 4 0 1 0 0 0 5 1 6 5 22

In enumerating these care must be taken to exclude cases where the ten squares do not form a connected whole and, where symmetry is possible, not to count the asymmetric cases twice.

For the record, the numbers of square-pieces of all sizes up to 24 were calculated, with a little computer help, by H. Redelmeier in 1981 (Discrete Mathematics, volume 36, pp191-203).