Title: Solve the equilateral triangles puzzle in C#

This post shows how a program can solve the puzzle Puzzle: Find the equilateral triangles in C#.

You can try to find the solutions manually, but some of them are pretty hard to visualize. This example uses the following code to find the solutions.

// Find the solutions. private void btnFindSolutions_Click(object sender, EventArgs e) { Cursor = Cursors.WaitCursor; Solutions = new List<int[]>(); for (int i = 0; i < Points.Length; i++) { for (int j = i + 1; j < Points.Length; j++) { double dx_ij = Points[j].X - Points[i].X; double dy_ij = Points[j].Y - Points[i].Y; double dist_ij = Math.Sqrt(dx_ij * dx_ij + dy_ij * dy_ij); for (int k = j + 1; k < Points.Length; k++) { double dx_jk = Points[k].X - Points[j].X; double dy_jk = Points[k].Y - Points[j].Y; double dist_jk = Math.Sqrt(dx_jk * dx_jk + dy_jk * dy_jk); const double tiny = 0.0001; if (Math.Abs(dist_ij - dist_jk) < tiny) { double dx_ki = Points[i].X - Points[k].X; double dy_ki = Points[i].Y - Points[k].Y; double dist_ki = Math.Sqrt(dx_ki * dx_ki + dy_ki * dy_ki); if (Math.Abs(dist_jk - dist_ki) < tiny) { // This is a solution. Solutions.Add(new int[] { i, j, k }); } } } } } lblNumSolutions.Text = Solutions.Count.ToString() + " solutions"; btnFindSolutions.Enabled = false; btnShowSolutions.Enabled = true; btnShowAllSolutions.Enabled = true; Refresh(); Cursor = Cursors.Default; }

The code uses three loops to loop over all off the unique triples of points. There are 12 points so there are 12 choose 3 = 220 unique triples.

The code calculates the distances between the pairs of points in each triple and, if the distances are the same, adds a new triangle holding the points to the solution list.

Note that the distances are floating point values and rounding errors often make floating point values look different when they should be the same. This is a common problem when working with floating point numbers. To avoid problems with equality testing, the code subtracts two distances, takes the absolute value, and checks whether the result is close to 0.

For example, when testing some of the points, the program finds these values that should be equal:

76.210235595703125 76.210235548698734

Subtracting those values gives 0.000000047004391490190756, which is smaller than the value tiny defined by this code as 0.0001, so the program treats the two values as equal. (In fact, this example is measuring distances in pixels so you could define tiny to be 1 and you would still find the correct solutions.)

Note that this method for searching for triangles relies on the fact that any three distinct points define a triangle. To see if they form an equilateral triangle you just need to see if the pairs are the same distances apart. Determining whether a set of points defines some other shape isn't as straightforward.

Seth Valdetero submitted a correct solution. His solution is included in this example's zip file.

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