This post shows how to solve the puzzle Puzzle: Find the squares in C#. The program howto_square_puzzle_solution 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 howto_find_squares 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.)

Todd Sabuncu submitted a correct solution. Click here to download it.

Pingback: Color the solutions to the "Find the squares in C#" puzzle - C# HelperC# Helper