Title: Tile a board with trominoes in C#

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ⁿ×2ⁿ (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¹×2¹ 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ⁿ⁺¹×2ⁿ⁺¹. Divide the board into four sub-boards with size 2ⁿ⁺¹×2ⁿ⁺¹. 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ⁿ×2ⁿ board.

By induction, that means the theorem applies for boards of size 2ⁿ×2ⁿ 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ⁿ).

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.

Download the example to experiment with it and to see additional details.