Trominoes are polyominoes of order three. That means they are polygons made up of three equal sized squares joined at their edges. There only are two kinds of trominoes: three squares joined in a line and three squares joined in an L shape. L-shaped trominoes also looks sort of like chairs, so that’s what I’ll call them here.

American mathematician Solomon W. Golomb devised Golomb’s Tromino Theorem, which states that you can tile any 2^{n}×2^{n} (n ≥ 1) chessboard that has one square removed with chair trominoes as shown in the picture at the top of this post.

The following sections describe the proof of Golomb’s Tromino Theorem and the code that the example program uses to find tilings.

# Proof

You can prove the theorem by induction, and that proof leads to a method for finding a tiling. For the base case, consider a 2^{1}×2^{1} board with one square removed. The following picture shows the four tilings that you might need to use depending on the location of the removed square.

Now suppose the theorem applies for n and consider the case of n + 1 so the board has size 2^{n+1}×2^{n+1}. Divide the board into four sub-boards with size 2^{n+1}×2^{n+1}. One of the quadrants holds the missing square. Place a tromino in the center squares of the three other sub-boards as shown in red in the following picture. Now each sub-board has one missing square. Because the theorem applies for those smaller sub-boards, we know that we can find a tiling for them, and that gives a tiling for the full 2^{n}×2^{n} board.

By induction, that means the theorem applies for boards of size 2^{n}×2^{n} for all n ≥ 1.

# Setup Code

The code to find the trominoes tilings is surprisingly complicated. The following code shows variables that the program uses to understand the board size.

// The quadrant that holds the square to be ignored. private enum Quadrants { NW, NE, SE, SW }; private int SquaresPerSide = 0; private float SquareWidth, BoardWidth, Xmin, Ymin; // The location of the missing square. private int MissingX, MissingY; private List<PointF[]> Chairs;

The `Quadrants` enumeration defines the four directions northwest, northeast, southeast, and southwest that we can use to keep track of a board’s quadrants.

The variable `SquaresPerSide` holds the number of squares on each side of the board. The variables `SquareWidth`, `BoardWidth`, `Xmin`, and `Ymin` hold values used to draw the board. For example, `Xmin` and `Ymin` give the upper left corner of the board.

Values `MissingX` and `MissingY` gives the row and column (starting from 0) of the missing square.

Finally, `Chairs` is a list of point arrays that represent the trominoes. For example, `Chairs[0]` is an array of points representing the first tromino.

When the program starts or when you click the Tile button, the following code finds a tiling.

// Make and solve a new board. private void Form1_Load(object sender, EventArgs e) { MakeBoard(); } private void btnTile_Click(object sender, EventArgs e) { MakeBoard(); } private void MakeBoard() { int n = int.Parse(txtN.Text); SquaresPerSide = (int)Math.Pow(2, n); // Set board parameters. SquareWidth = (picBoard.ClientSize.Width - 10f) / SquaresPerSide; float hgt = (picBoard.ClientSize.Height - 10f) / SquaresPerSide; if (SquareWidth > hgt) SquareWidth = hgt; BoardWidth = SquareWidth * SquaresPerSide; Xmin = (picBoard.ClientSize.Width - BoardWidth) / 2; Ymin = (picBoard.ClientSize.Height - BoardWidth) / 2; // Pick a random empty square. Random rand = new Random(); MissingX = rand.Next(SquaresPerSide); MissingY = rand.Next(SquaresPerSide); // Solve the board. Chairs = new List<PointF[]>(); SolveBoard( 0, SquaresPerSide - 1, 0, SquaresPerSide - 1, MissingX, MissingY); // Redraw. picBoard.Refresh(); }

The form’s `Load` event handler and the Tile button’s `Click` event handler call the `MakeBoard` method. That method gets the value for `n` that you entered in the text box and calculates the number of squares per side (2^{n}).

Next, the method calculates the size that a square would have if the board fills the picture box horizontally. It also calculates the size a square would have if the board fills the picture box vertically, and sets `SquareWidth` to the smaller of the two sizes so the board will fit. It then uses the size to calculate `Xmin` and `Ymin` to center the board in the drawing area.

The method then uses a `Random` object to pick a random row and column to hold the missing square. It then creates a new `Chairs` list and calls `SolveBoard` to find a tiling. The method finishes by refreshing the `picBoard` picture box to show the solution.

# SolveBoard

The following code shows the `SolveBoard` method.

// Solve the board. private void SolveBoard(int imin, int imax, int jmin, int jmax, int imissing, int jmissing) { // See if this is a 2x2 square. if (imax - imin == 1) { // It is a 2x2 square. Make its chair. Chairs.Add(MakeChair(imin, imax, jmin, jmax, imissing, jmissing)); return; } // Not a 2x2 square. Divide into 4 pieces and recurse. int imid = (imin + imax) / 2; int jmid = (jmin + jmax) / 2; switch (QuadrantToIgnore(imin, imax, jmin, jmax, imissing, jmissing)) { case Quadrants.NW: // Make the chair in the middle. Chairs.Add(MakeChair(imid, imid + 1, jmid, jmid + 1, imid, jmid)); // Recurse. SolveBoard(imin, imid, jmin, jmid, imissing, jmissing); // NW SolveBoard(imid + 1, imax, jmin, jmid, imid + 1, jmid); // NE SolveBoard(imid + 1, imax, jmid + 1, jmax, imid + 1, jmid + 1); // SE SolveBoard(imin, imid, jmid + 1, jmax, imid, jmid + 1); // SW break; case Quadrants.NE: // Make the chair in the middle. Chairs.Add(MakeChair(imid, imid + 1, jmid, jmid + 1, imid + 1, jmid)); // Recurse. SolveBoard(imin, imid, jmin, jmid, imid, jmid); // NW SolveBoard(imid + 1, imax, jmin, jmid, imissing, jmissing); // NE SolveBoard(imid + 1, imax, jmid + 1, jmax, imid + 1, jmid + 1); // SE SolveBoard(imin, imid, jmid + 1, jmax, imid, jmid + 1); // SW break; case Quadrants.SE: // Make the chair in the middle. Chairs.Add(MakeChair(imid, imid + 1, jmid, jmid + 1, imid + 1, jmid + 1)); // Recurse. SolveBoard(imin, imid, jmin, jmid, imid, jmid); // NW SolveBoard(imid + 1, imax, jmin, jmid, imid + 1, jmid); // NE SolveBoard(imid + 1, imax, jmid + 1, jmax, imissing, jmissing); // SE SolveBoard(imin, imid, jmid + 1, jmax, imid, jmid + 1); // SW break; case Quadrants.SW: // Make the chair in the middle. Chairs.Add(MakeChair(imid, imid + 1, jmid, jmid + 1, imid, jmid + 1)); // Recurse. SolveBoard(imin, imid, jmin, jmid, imid, jmid); // NW SolveBoard(imid + 1, imax, jmin, jmid, imid + 1, jmid); // NE SolveBoard(imid + 1, imax, jmid + 1, jmax, imid + 1, jmid + 1); // SE SolveBoard(imin, imid, jmid + 1, jmax, imissing, jmissing); // SW break; } }

This method’s parameters indicate what part of the full board that this method call must tile with trominoes. The parameters `imin` and `imax` give the smallest and largest column numbers of interest. Similarly, `jmin` and `jmax` give the smallest and largest row numbers of interest.

The parameters `imissing` and `jmissing` give the column and row of the square that is missing from this part of the board. Note that this square might actually be missing in the full board, or it might be a square that we should ignore while tiling this part of the board because it has already been covered by the red tromino in the earlier picture.

If the method is trying to tile a 2×2 board, it simply calls the `MakeChair` method described later to create a tromino for the board. It adds that tromino to the `Chairs` list and returns.

If the board is larger than 2×2, the code finds the row and column of the middle of the board. Because this calculation uses integer division, `imid` and `jmid` give the largest column and row in the upper left quadrant.

Next, the code calls the `QuadrantToIgnore` method described later to see which quadrant contains the square that we should ignore. The method uses a `switch` statement to determine how to position the red tromino and recursively call itself as shown in the earlier picture.

This is the trickiest section of code. If the calls are incorrect, the result isn’t a tiling and figuring out exactly what went wrong is very difficult. The best approach to this code is to just walk through it very carefully and make sure there are no mistakes the first time.

For each case, the code calls the `MakeChair` method to make a polygon for the red tromino shown in the earlier picture and adds that polygon to the `Chairs` list.

The `SolveBoard` method then calls itself recursively to tile the four sub-boards with trominoes. It adjusts the `imin`, `imax`, `jmin`, and `jmax` arguments to make the calls visit the sub-boards. It changes the `imissing` and `jmissing` arguments to make the recursive calls ignore the appropriate squares. For the sub-board that contains the square that the original call to `SolveBoard` was supposed to ignore, that recursive call still ignores that square. For the other sub-boards, the recursive call ignores the square covered by the red tromino in the earlier picture.

# MakeChair

The `MakeChair` method returns an array of points representing a tromino within a 2×2 sub-board. It took me a while to find a nice solution that can draw any of the trominoes we might need. Instead of using a `switch` statement to return one of four complicated lists of points, I decided to make a single set of points representing the square on the left in the following picture.

Then the method moves one of the corner points to the center of the sub-board. The picture on the right above shows how it modifies the points when the square to ignore is in the northeast quadrant. (The resulting polygon includes two points that it really doesn’t need in the middle of two of the chair’s sides, but they don’t hurt much so I won’t go to the trouble of removing them.)

The following code shows the `MakeChair` method.

// Make a chair polygon. private PointF[] MakeChair(int imin, int imax, int jmin, int jmax, int imissing, int jmissing) { // Make the initial points. float xmin = Xmin + imin * SquareWidth; float ymin = Ymin + jmin * SquareWidth; PointF[] points = { new PointF(xmin, ymin), new PointF(xmin + SquareWidth, ymin), new PointF(xmin + SquareWidth * 2, ymin), new PointF(xmin + SquareWidth * 2, ymin + SquareWidth), new PointF(xmin + SquareWidth * 2, ymin + SquareWidth * 2), new PointF(xmin + SquareWidth, ymin + SquareWidth * 2), new PointF(xmin, ymin + SquareWidth * 2), new PointF(xmin, ymin + SquareWidth), }; // Push in the appropriate corner. PointF middle = new PointF( xmin + SquareWidth, ymin + SquareWidth); switch (QuadrantToIgnore(imin, imax, jmin, jmax, imissing, jmissing)) { case Quadrants.NW: points[0] = middle; break; case Quadrants.SW: points[6] = middle; break; case Quadrants.NE: points[2] = middle; break; case Quadrants.SE: points[4] = middle; break; } return points; }

The method first sets `xmin` and `ymin` to the X and Y coordinates of the sub-board’s upper left point. It then creates an array holding the points shown on the left in the earlier picture.

Next, the method finds the sub-board’s midpoint. It then calls the `QuadrantToIgnore` method described shortly to figure out which quadrant contains the square that we should ignore. It then uses a `switch` statement to move the appropriate corner point to the sub-board’s midpoint.

# QuadrantToIgnore

The `QuadrantToIgnore` method determines which quadrant of a sub-board contains the square that you should ignore when tiling the sub-board with trominoes. The following code shows the method.

// Return the quadrant holding the square to be ignored for this square. private Quadrants QuadrantToIgnore(int imin, int imax, int jmin, int jmax, int imissing, int jmissing) { int imid = (imin + imax) / 2; int jmid = (jmin + jmax) / 2; if (imissing <= imid) // West. { if (jmissing <= jmid) return Quadrants.NW; return Quadrants.SW; } else // East. { if (jmissing <= jmid) return Quadrants.NE; return Quadrants.SE; } }

The method sets `imid` and `jmid` to the column and row at the center of the sub-board. Because the calculation uses integer division, `imid` and `jmid` give the largest column and row in the upper left quadrant.

The code then uses a simple set of `if` statements to determine which quadrant contains the missing square.

# Drawing the Trominoes

The program’s last piece is the following `Paint` event handler, which draws the tilings trominoes.

// Draw the board. private void picBoard_Paint(object sender, PaintEventArgs e) { e.Graphics.Clear(picBoard.BackColor); e.Graphics.SmoothingMode = SmoothingMode.AntiAlias; // Draw the chairs. foreach (PointF[] points in Chairs) { e.Graphics.DrawPolygon(Pens.Red, points); } // Draw the missing square. float x = Xmin + MissingX * SquareWidth; float y = Ymin + MissingY * SquareWidth; e.Graphics.FillRectangle(Brushes.Black, x, y, SquareWidth, SquareWidth); }

This code clears the `Graphics` object and prepares it to draw smoothly. It then loops through the trominoes in the `Chairs` list and draws each polygon in red.

The method finishes by filling the missing square with black.

# Conclusion

The proof that a tiling with trominoes is possible is relatively straightforward, at least if you’re familiar with inductive proofs. The proof leads naturally to a recursive method to finding a tiling, but the details are a bit tricky. In particular, if you make any mistakes in the `SolveBoard` method’s recursive calls, the result isn’t a tiling and figuring out what went wrong is hard.

In my next post, I’ll explain how you can color the trominoes so that no two adjacent trominoes have the same color.

Pingback: Tile a board with colored trominoes in C# - C# HelperC# Helper