Title: Solve the "Find the squares in C#" puzzle

This post shows how to solve the puzzle Puzzle: Find the squares in C#. The program uses the following code to define the puzzle's 11 solutions.

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

You can try to find the solutions manually but two of them are fairly hard to spot. The program uses the following code to find the solutions.

// Find the solutions. private void FindSolutions() { for (int i = 0; i < Points.Length - 3; i++) { for (int j = i + 1; j < Points.Length - 2; j++) { for (int k = j + 1; k < Points.Length - 1; k++) { for (int m = k + 1; m < Points.Length; m++) { // See if these points make a square. int[] square_points = GetSquarePoints(i, j, k, m); if (square_points != null) { Solutions.Add(square_points); } } } } } }

This code simply loops through all sets of four distinct points and calls the GetSquarePoints method for the set. The GetSquarePoints method determines whether the points with the given indexes form a square and, if they do, returns an array holding the indexes in an order that forms a square. (For example, if A-B-C-D forms a square, then A-B-D-C does not.)

The picture on the right shows how the GetSquarePoints method works. Consider the point i. If this is a square, then the distances between point i and points j and m must be the same. Suppose that distance is S. Because the triangle Δikm is a 45-45-90 triangle. That means the distance between points i and m is S√2.

Knowing that little bit of geometry, you can understand the following GetSquarePoints method.

// If these points make up a square, return an array holding // them in an order that makes a square. // If the points don't make up a square, return null. private int[] GetSquarePoints(int i, int j, int k, int m) { // A small value for equality testing. const double tiny = 0.001; // Store all but the first index in an array. int[] indexes = { j, k, m }; // Get the distances from point i to the others. float[] distances = { PointFDistance(Points[i], Points[j]), PointFDistance(Points[i], Points[k]), PointFDistance(Points[i], Points[m]), }; // Sort the distances and the corresponding indexes. Array.Sort(distances, indexes); // If the two smaller distances are not roughly // the same (the side length), then this isn't a square. if (Math.Abs(distances[0] - distances[1]) > tiny) return null; // If the longer distance isn't roughly Sqr(2) times the // side length (the diagonal length), then this isn't a square. float diagonal_length = (float)(Math.Sqrt(2) * distances[0]); if (Math.Abs(distances[2] - diagonal_length) > tiny) return null; // See if the distance between the farther point and // the two closer points is roughly the side length. float distance1 = PointFDistance(Points[indexes[2]], Points[indexes[0]]); if (Math.Abs(distances[0] - distance1) > tiny) return null; float distance2 = PointFDistance(Points[indexes[2]], Points[indexes[1]]); if (Math.Abs(distances[0] - distance2) > tiny) return null; // It's a square! return new int[] { i, indexes[0], indexes[2], indexes[1] }; }

The method picks the first point arbitrarily to be point i. It calls the PointFDistance method to calculate the distances between point i and the other points. (PointFDistance is straightforward so it isn't shown here. Download the example to see how it works.)

The code then calls Array.Sort to sort the array of distances between the points. It passes an array holding the points' indexes to Array.Sort so that method can arrange the indexes so they correspond to the sorted distances. In other words, after sorting, the distance from point i to point indexes[0] is in distances[0].

Next, the code verifies that the distances to the two closer points (j and m in the picture) are the same (call it S) and that the distance to the farther point is S√2. The code finishes by determining whether the farther point (k in the picture) is distance S from the other two points.

All of these facts are consistent with a square. The only remaining question is, could there be some other points that satisfy these conditions?

Because the diagonal's length is S√2, we know that the triangles Δijk and Δimk are 45-45-90 triangles. Because those triangles share the edge i-k, the triangles are either as shown in the picture or they are the same triangle. We know they are not the same triangle because the FindSolutions method generates sets of points that do not contain duplicates so we know we have a square. (If FindSolutions created sets of four points that could contain duplicates, then you could also test that the diagonal j-m also had length S√2.)

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