Solve the equilateral triangles puzzle in C#


[puzzle]

This post shows how to solve and display the solutions to the puzzle Puzzle: Find the equilateral triangles in C#. This example uses the following code to define the puzzle’s 25 solutions.

// Define the solutions.
Solutions = new List<int[]>();
Solutions.Add(new int[] { 0, 2, 3 });
Solutions.Add(new int[] { 0, 3, 1 });
Solutions.Add(new int[] { 1, 3, 4 });
Solutions.Add(new int[] { 2, 5, 6 });
Solutions.Add(new int[] { 2, 6, 3 });
Solutions.Add(new int[] { 3, 6, 7 });
Solutions.Add(new int[] { 3, 7, 4 });
Solutions.Add(new int[] { 4, 7, 8 });
Solutions.Add(new int[] { 5, 9, 6 });
Solutions.Add(new int[] { 6, 9, 10 });
Solutions.Add(new int[] { 6, 10, 7 });
Solutions.Add(new int[] { 7, 10, 11 });
Solutions.Add(new int[] { 7, 11, 8 });

Solutions.Add(new int[] { 0, 5, 7 });
Solutions.Add(new int[] { 1, 6, 8 });
Solutions.Add(new int[] { 3, 9, 11 });
Solutions.Add(new int[] { 10, 2, 4 });

Solutions.Add(new int[] { 5, 10, 3 });
Solutions.Add(new int[] { 2, 7, 1 });
Solutions.Add(new int[] { 6, 11, 4 });
Solutions.Add(new int[] { 8, 3, 10 });
Solutions.Add(new int[] { 4, 6, 0 });
Solutions.Add(new int[] { 7, 9, 2 });

Solutions.Add(new int[] { 0, 9, 8 });
Solutions.Add(new int[] { 1, 5, 11 });

This code defines the variable Solutions to be a list containing arrays of integers. It then adds to the list arrays containing the indexes of the points that make up the solutions.

You can try to find the solutions manually, but some of them are pretty hard to visualize. The example howto_find_equilateral_triangles 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. Click here to download Seth’s solution.


Download Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in algorithms, games, graphics, mathematics and tagged , , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *