Abstract

The game called "New Tetris", for Nintendo 64 lets a player drop Tetris pieces, which are 4-celled polyominoes, or tetrominoes, into a rectangular playing field.  The objective is to complete "rows" by densely packing the pieces so that all 10 cells in a given row are covered by a tetromino.  Higher scores can be achieved by first packing the tetrominoes into perfect 4-by-4 squares, which glow gold (when packed with four identical tetrominoes) or silver (otherwise), and then afterwards completing the rows that contain the gold or silver 4-by-4 squares.  In playing the game, I was struck by the wide variety of combinations of Tetris pieces that can be used to form gold and silver squares.  By hand, I drew diagrams of 35 such tilings, and then I designed an Excel spreadsheet that found two others, for a total of 37 — 8 golden tilings, and 29 silver ones.

This page describes the ways to tile an n-by-n square with one-sided polyominoes with n cells (n-polyominoes).  Two tilings are considered distinct if neither one is a rotation of the other.  OEIS doesn't seem to contain the sequence of the numbers of such n-tilings for n=1, 2, 3, 4, ...  This sequence is 1, 1, 3, 37, ...

To be sure that 37 is the correct number of distinct tilings of a 4-by-4 square by Tetris pieces, I designed an Excel spreadsheet that enumerated all 113 ways to position one of the 29 fixed tetrominoes within a 4-by-4 square.  I call each of these 113 ways a "positioning".  Then I superimposed all 113*112/2 distinct pairs of positionings to find those without any overlapping.  Finally, I matched up those pairs of positionings with other pairs that completely filled the square.  I then eliminated all but one of each tiling that can be obtained by rotating other tilings to arrive at 37 tilings.

The organization of this page is as follows:

Section 1: Enumeration of one-sided n-polyominoes, and diagrams of all distinct tilings of n-by-n squares by these pieces, for n=0,1,2,3,4, and maybe someday, 5.

Section 2: Detailed description of the method of finding distinct tilings of an n-by-n square by n-polyominoes, for n=0,1,2,3,4, and 5.

Section 3: Odds and Ends: Interesting factoids that arose in connection with this topic.

Section 1: Enumeration of n-polyomino tilings of an n-by-n square

This section enumerates one-sided n-polyominoes, and diagrams of all distinct tilings of n-by-n squares by these pieces, for n=0,1,2,3,4, and maybe someday, 5.

0-celled one-sided polyomino (the null polyomino) and the one tiling of a 0-by-0 square with 0-polyominoes

What?  You didn't see it?  It's there, trust me, just above this paragraph, and below the title.  It's just too small to see.  Just as there is exactly one null set, there is exactly one 0-celled one-sided polyomino.

But the number of such polyominoes required to tile a 0-by-0 square is arbitrary.  For example, you can easily fit five 0-celled polyominoes inside a 0-by-0 square without overlapping them (except at their borders).

So the n=0 case is undefined.  I'm really sorry to start Section 1 with such a deep exercise in abstract thinking.  Don't worry, it gets much better.

1-celled one-sided polyomino and the one tiling of a 1-by-1 square

There is just one 1-celled polyomino, and one way to use it to tile a 1-by-1 square:

2-celled one-sided polyomino and the one tiling of a 2-by-2 square

There is just one 2-celled polyomino, and one way to use it to tile a 2-by-2 square:

Remember, tilings are considered distinct only if none can be obtained by rotating another.

3-celled one-sided polyominoes and the three tilings of a 3-by-3 square

There are two 3-celled polyominoes, and three ways to use them to tile a 3-by-3 square:

The distinction between one-sided and free polyominoes isn't important for 1-, 2-, and 3-celled polyominoes because all of these small pieces have bilateral symmetry.  This distinction becomes important only for 4-celled and larger polyominoes.  There are five 4-celled free polyominoes.  Two of them lack bilateral symmetry, so their mirror images form two of the seven 4-celled one-sided polyominoes.

4-celled one-sided polyominoes, popularized by "The New Tetris" game for Nintendo-64 (there are 7 of them)

There are seven 4-celled one-sided polyominoes:

The 37 ways to tile a 4-by-4 square with Tetris pieces

Summary of Section 1

The sequence of the number of ways to tile an n-by-n square with one-sided polyominoes with n cells (n-polyominoes) for n=1,2,3,4,... is 1,1,3,37,...  Note: two tilings are considered distinct if neither one is a rotation of the other.

Section 2: Method of finding distinct tilings of an n-by-n square by one-sided n-polyominoes

Section 2: Detailed description of the method of finding distinct tilings of an n-by-n square by n-polyominoes, for n=0,1,2,3,4, and maybe someday, 5.

This section is currently under construction . . . . . . . .

Overview

(an overview will be created later.)

Section 3: Odds and Ends

Odds and ends are interesting factoids that arose in connection with this topic.

Chiral

Merriam-Webster defines chiral as: of, relating to, or being a molecule that is nonsuperimposable on its mirror image.  Of polyominoes, the word is used to describe ones that are distinct — or considered distinct — from their mirror images.  OEIS applies the word to the sequence of numbers of one-sided polyominoes with n cells to mean that some of the polyominoes for each n are chiral in that they are considered distinct from their mirror images.  The description of A000988 is: Number of one-sided (or chiral) polyominoes with n cells.  When n is 4, for example, there are two pairs of chiral tetrominoes: L,J and Z,S.  Together with the I, O, and T, there are 7 one-sided tetrominoes.  Compare this to A000105, the Number of polyominoes with n cells, which considers L and J to be the same, and Z and S to be the same.  Viewed this way, there are five tetrominoes: L, Z, I, O, and T.  None of them are chiral, because none of them is considered distinct from its mirror image.

I think the polyomino entries in OEIS should be changed as follows.

A000988, the number of n-celled one-sided polyominoes, uses the word "chiral" in a misleading way. Chiral means distinct from its mirror image. True, it is reasonable to characterize free polyominoes (A000105) as non-chiral in that no free polyomino is considered distinct from its mirror image. However not all one-sided polyominoes (A000988) are chiral. In fact, a better sequence to describe chiral polyominoes is A030228, which are the polyominoes lacking bilateral symmetry.

I suggest removing the word "chiral" from the description of A000988, and adding the following comment to all three sequences, along with appropriate cross-references (I checked later, and found these suggestions were adopted):

A000105(n) + A030228(n) = A000988(n) because the number of free polyominoes plus the number of polyominoes lacking bilateral symmetry equals the number of one-sided polyominoes.

Internet References

Tetriswiki: Square_Platforming 

OEIS: A000105 — number of polyominoes with n cells - 1, 1, 1, 2, 5, 12, ...

OEIS: A000988 — number of one-sided polyominoes with n cells - 1, 1, 1, 2, 7, 18, ...

Wikipedia: Polyomino is a clear description of polyominoes — free, one-sided, and fixed.

Wikipedia: Tetromino describes 4-celled polyominoes — the one-sided ones are the seven Tetris pieces.

Related pages in this website

Go Up to Counting

Polyominoes enumerates and classifies polyominoes by their bilateral and rotational symmetries, and the size of the smallest rectangle that encloses them.

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]