Title: Tile a board with colored trominoes in C#

The post Tile a board with trominoes in C# explains how to tile a board with a missing square with trominoes. This post shows how to color the trominoes so no two adjacent ones share the same color.

The four-color theorem states that you can color any map (separation of a plane into contiguous regions) with only four colors. (The theorem was proposed in 1852 but only proven in 1976.) Unfortunately the proof is very long, complicated, and computer assisted, so it does not give a practical method for finding a coloring.

My book Essential Algorithms describes several approaches for coloring maps including a five-coloring algorithm.

Another approach is to simply iterate through every possible combination of colors until you find one that works. In general, this can be slow. If a map has N regions and you want to use C colors, then there are C^N possible combinations of colors and that can be a very large number. For example, there are currently 195 countries in the world. If you want to color them with four colors, then there are 4¹⁹⁵ ≈ 2.5×10¹¹⁷ possible combinations to consider.

Fortunately, many maps are smaller and many are relatively easy to color so the program doesn't need to examine every possible combination.

To color the trominoes, this program must perform two main tasks: finding the trominoes' neighbors and finding a valid coloring.

Finding the Trominoes' Neighbors

The previous example created an array of PointF to represent each tromino. To determine which trominoes are neighbors, you could loop through every pair of trominoes and then see if they share a common edge. To see if they share an edge, you could see if any of the adjacent pairs of points in the first tromino matched any adjacent pair in the second tromino. When you considered a pair of edges, you would need to check to see if one of the edges was backwards. You would also need to check for approximate matches caused by rounding errors.

That all seemed inelegant and a lot of work, so I took a different approach. When the program creates a chair shape, it knows which rows and columns on the board that chair occupies. To make it easier to find neighbors, I created a Chair class to represent the trominoes. The class stores a chair's points and the squares that it occupies.

The following code shows the beginning of the Chair class.

public class Chair { public static Brush[] BgBrushes = { Brushes.Red, Brushes.Blue, Brushes.Yellow, }; public int Number; public int BgBrushNum = 0; public List<Point> Squares = new List<Point>(); public PointF[] Points; public List<Chair> Neighbors;

The class declares a static array of brushes that it will use to color the trominoes. I believe (but have not proven formally) that you can always color a tromino tiling with only three colors, so the array only contains red, blue, and yellow.

Next, the class declares chair properties such as the chair's number and brush index in the array. The Squares list holds the squares that the chair occupies. The X and Y coordinates of the points in the list give the squares' rows and columns on the board.

The Points array holds the chair's polygon points as before. The Neighbors list will indicate the Chairs that share an edge with this one.

The class also defines methods to perform such tasks as drawing the chair. Download the example and look at the code to see how that works. For now, I only want to described two more methods.

The following AreNeighbors method returns true if two squares share a common edge.

// Return true if the two squares are neighbors. public static bool AreNeighbors(Point p1, Point p2) { if ((p1.X == p2.X) && (Math.Abs(p1.Y - p2.Y) == 1)) return true; if ((p1.Y == p2.Y) && (Math.Abs(p1.X - p2.X) == 1)) return true; return false; }

If the two squares are in the same row and their columns differ by one, then they are adjacent horizontally so the method returns true.

Similarly, if the two squares are in the same column and their rows differ by one, then they are adjacent vertically so the method returns true.

If neither of those tests makes the method return true, then the squares are not adjacent so the method returns false.

The second method is the following IsNeighbor method, which returns true if the current chair shares an edge with another chair.

// Return true if the two Chairs are neighbors. public bool IsNeighbor(Chair other) { foreach (Point p1 in Squares) foreach (Point p2 in other.Squares) if (AreNeighbors(p1, p2)) return true; return false; }

This method simply loops through all of the squares occupied by both chairs and calls the AreNeighbors method to see if any of the squares are neighbors.

The main program uses the following FindNeighbors method to finds the trominoes' neighbors.

// Find the Chairs' neighbors. private void FindNeighbors() { int num_chairs = Chairs.Count; // Create empty Neighbors lists. foreach (Chair chair in Chairs) chair.Neighbors = new List<Chair>(); // Find neighbors. for (int i = 0; i < num_chairs - 1; i++) { for (int j = i + 1; j < num_chairs; j ++) { if (Chairs[i].IsNeighbor(Chairs[j])) { Chairs[i].Neighbors.Add(Chairs[j]); Chairs[j].Neighbors.Add(Chairs[i]); } } } }

The method first loops through its Chairs list, which holds a reference to each Chair object and sets each chair's Neighbors list to an empty list.

Next, the code loops through every pair of distinct chairs and calls uses the Chair class's IsNeighbor method to determine whether the two chairs are neighbors. If they are neighbors, the method adds each chair to the other's Neighbors list.

Finding a Valid Coloring

After you know which trominoes are adjacent to which others, finding a coloring is just a matter of trying possibilities. The following FindColoring method starts the process.

// Find a coloring of the Chairs. private void FindColoring() { // Find the neighbors. FindNeighbors(); // Give each Chair color number -1. foreach (Chair chair in Chairs) chair.BgBrushNum = -1; // Assign colors. if (!FindColoring(0)) MessageBox.Show("Could not find coloring."); }

The method first calls the FindNeighbors method described earlier. It then loops through the chairs and sets all of their BgBrushNum properties to -1 to indicate that they do not have an assigned color.

The method finishes by calling the following FindColoring method. It passes that method the parameter 0 to indicate that it should start assigning a color to the first chair.

// Find a coloring of the Chairs starting from Chair // number start_chair Return true if we find a coloring. private bool FindColoring(int start_chair) { // If we are beyond the end of the Chairs list, we are done. if (start_chair == Chairs.Count) return true; // Try each of the colors for this Chair. int num_colors = Chair.BgBrushes.Length; Chair this_chair = Chairs[start_chair]; for (int color_num = 0; color_num < num_colors; color_num++) { if (this_chair.ColorAllowed(color_num)) { this_chair.BgBrushNum = color_num; if (FindColoring(start_chair + 1)) return true; } } // We failed to find a coloring. Backtrack. this_chair.BgBrushNum = -1; return false; }

This method recursively assigns colors to chairs starting with chair number start_chair. The method first checks to see if it is finished. If chair_number equals the total number of chairs, then every chair has been assigned a color so the method returns true to indicate that it has found an assignment.

If the method is not finished, it loops through the numbers that represent the allowed color indices. In the example as it is written, the colors in the Chair.BgBrushes array have indices 0 through 2, so the loop ranges from 0 to 2.

Inside the loop, the code calls the current chair's ColorAllowed method (described shortly) to see if that chair can have the color that is currently being examined by the loop. If the chair could have that color, the method tentatively assigns the chair that color and then recursively calls itself to assign the next chair's color.

If the recursive call returns true, then it found a valid coloring so the method also returns true to unwind the recursion.

If the loop ends with none of the colors leading to a valid coloring, the method resets the chair's color to -1 and returns false. A call higher up the call stack will change the color of the chair it is examining and the recursive calls will try again until they find a valid coloring or until all combinations have been tried unsuccessfully.

The Chair class defines the following ColorAllowed method, which returns true if the chair can have a certain color.

// Return true if this Chair could have this color number. public bool ColorAllowed(int color_num) { foreach (Chair chair in Neighbors) if (chair.BgBrushNum == color_num) return false; return true; }

This method simply loops through the chair's neighbors and returns false if any of those neighbors have the color color_num. If none of the neighbors have been assigned that color, the method returns true.

Conclusion

The program includes a few other details (such as the pieces described in the earlier post, but those are the most interesting new pieces. Download the example program to see additional details. You can also experiment with the program. See if you can find an instance where you need more than three colors to color the trominoes. Or post a comment if you figure out how to prove that three colors is enough.

In my next post, I'll explain how you can randomize the colors. That allows the program to find more three-color arrangements or to use more than three colors.

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