Title: Puzzle: Find the equilateral triangles in C#

This is a puzzle that I heard a while back on National Public Radio (NPR). How many equilateral triangles can you make with corners on the points drawn by the program? For this blog, the puzzle has two parts. First see if you can solve the puzzle "manually." Then write a program that solves the puzzle.

The code available for download with this post draws the points and will draw the solution after you fill in the appropriate code. You only need to fill in a small piece of code that initializes the solution, or better yet discovers the solution for you.

The rest of this post shows how parts of the program that I've written for you work. The following code executes when the form loads. (This is where you need to add your code.)

// The points. private PointF[] Points; // The solutions. private List<int[]> Solutions; // The solution we should display. private int CurrentSolution = 100; // Define the points and solutions. private void Form1_Load(object sender, EventArgs e) { DoubleBuffered = true; // Define the points. float dy = ClientSize.Height / 4; float dx = (float)(dy / Math.Sqrt(3)); float top_x = ClientSize.Width / 2; float top_y = -dy / 2; Points = new PointF[] { new PointF(top_x - dx, top_y + dy), new PointF(top_x + dx, top_y + dy), new PointF(top_x - 2 * dx, top_y + 2 * dy), new PointF(top_x - 0 * dx, top_y + 2 * dy), new PointF(top_x + 2 * dx, top_y + 2 * dy), new PointF(top_x - 3 * dx, top_y + 3 * dy), new PointF(top_x - 1 * dx, top_y + 3 * dy), new PointF(top_x + 1 * dx, top_y + 3 * dy), new PointF(top_x + 3 * dx, top_y + 3 * dy), new PointF(top_x - 2 * dx, top_y + 4 * dy), new PointF(top_x - 0 * dx, top_y + 4 * dy), new PointF(top_x + 2 * dx, top_y + 4 * dy), }; // Define the solutions. Solutions = new List<int[]>(); // Insert your code here... }

This code creates the Points array that defines the points. The points are numbered from top to bottom and left to right so the points in the first row have indices 0 and 1, the points in the second row have indices 2, 3, and 4, and so forth.

This code also creates an empty Solutions list. Your code should add arrays of three integers to the list to indicate the indices of points that make up the triangles. For example, the following statement adds a triangle to the list that uses points 0, 2, and 3.

Solutions.Add(new int[] { 0, 2, 3 });

The program uses the following Paint event handler to draw the points and the solution triangle indicated by the CurrentSolution variable.

// Draw the circles and any triangles currently defined. private void Form1_Paint(object sender, PaintEventArgs e) { e.Graphics.SmoothingMode = SmoothingMode.AntiAlias; // Draw the points. const float radius = 5; foreach (PointF pt in Points) { e.Graphics.FillEllipse(Brushes.Blue, pt.X - radius, pt.Y - radius, 2 * radius, 2 * radius); } // Draw the current solution. if (CurrentSolution < 0) { // Draw all solutions. for (int i = 0; i < Solutions.Count; i++) { DrawSolution(e.Graphics, i); } } else { // Draw the current solution. DrawSolution(e.Graphics, CurrentSolution); } }

This code loops through the points and draws them. Then if CurrentSolution is less than 0, the program loops through all of the solutions and calls DrawSolution for each. If CurrentSolution is not less than 0, the program calls DrawSolution to draw just that solution.

The following code shows how the DrawSolution method draws a particular solution.

// Draw a solution. private void DrawSolution(Graphics gr, int solution_num) { if (solution_num >= Solutions.Count) return; // Make a list of the points in this solution. List<PointF> pts = new List<PointF>(); foreach (int i in Solutions[solution_num]) pts.Add(Points[i]); gr.DrawPolygon(Pens.Red, pts.ToArray()); }

If the solution number passed to the method is not a valid solution index, the method returns without doing anything.

If the solution number is valid, the code creates a List of PointF. It loops through the indices stored in the indicated solution and adds their points to the list. It then calls the Graphics object's DrawPolygon method to draw the points. DrawPolygon works with arrays not lists so the code calls the list's ToArray method to convert it into an array.

The rest of the program's code is reasonably straightforward.

// Start showing solutions. private void btnShowSolutions_Click(object sender, EventArgs e) { // Disable the button. btnShowSolutions.Enabled = false; // Start at the first solution. CurrentSolution = 0; // Start the timer. tmrChangeSolution.Enabled = true; // Redraw. Refresh(); } // Show the next solution. private void tmrChangeSolution_Tick(object sender, EventArgs e) { // Increment CurrentSolution. If the result is greater than // the last solution's index, disable the timer. tmrChangeSolution.Enabled = (++CurrentSolution < Solutions.Count); // If we're done drawing, enable the button. btnShowSolutions.Enabled = (!tmrChangeSolution.Enabled); // Redraw. Refresh(); } // Show all of the solutions. private void btnShowAllSolutions_Click(object sender, EventArgs e) { CurrentSolution = -1; tmrChangeSolution.Enabled = false; btnShowSolutions.Enabled = true; Refresh(); }

When you click the Show Solutions button, the program disables that button so you can't press it again. It then sets CurrentSolution = 0 to display the first solution, enables the tmrChangeSolution Timer, and refreshes the form to redraw. The Paint event handler draws the selected solution (number 0). If there are no solutions, then the DrawSolution method draws nothing because the index 0 is not a valid index in the Solutions list.

When the timer ticks, the program increments CurrentSolution. It sets the Timer component's Enabled property to true if the new value is still a valid solution index so the Timer runs until the last solution has been displayed. If the timer is no longer enabled, the code re-enables the Show Solutions button. The Tick event handler finishes by refreshing the form to redraw it.

Finally if when you click the Show All button, the program sets CurrentSolution to -1 and refreshes to redraw the solution. If you look back at the Paint event handler, you'll see that it calls DrawSolution for every solution if CurrentSolution < 0.

Download the example program and try to solve the puzzle. You can explicitly enter code to create solutions that you figured out yourself, or you can write code to find all of the solutions. Here's a small hint: There are more solutions than you will probably think of at first.

I'll post my solutions (manually solved and automatically solved) in about a week.

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