This post relates to two of my books.
Essential Algorithms, Second Edition describes many fascinating algorithms in pseudocode with source code available for download in Python and C#.	Interview Puzzles Dissected: Solving and Understanding Interview Puzzles describes interview puzzles, some of which are somewhat simmilar to the squares puzzle, and explains how to solve them. (Manually, not necessarily with a program.)

Title: Solve a squares puzzle in Python

[You must connect the 12 dots to make as many squares as possible.]

The goal of the squares puzzle is to figure out how many squares you can make by connecting quadruples of the points shown in the picture.

If you're doing this manually, it's pretty easy to spot the squares. The trick is not losing track of which squares you've already counted. Before you read on, you might see how many of the squares you can find.

To find the solutions, the program enumerates every possible quadruple of points and determines whether they form a square. The following find_solutions method performs the enumeration.

def find_solutions(points): '''Find the solutions.''' solutions = [] for a in range(len(points)): for b in range(a + 1, len(points)): for c in range(b + 1, len(points)): for d in range(c + 1, len(points)): # See if these points make a square. square_points = get_square_points( points[a], points[b], points[c], points[d]) if square_points is not None: solutions.append(square_points) return solutions

This method uses four nested for loops to iterate through quadruples of points. As was the case when enumerating points in the post Solve an equilateral triangle puzzle in Python, the loops keep the point indices ordered so a < b < c < d. You could order four points in several ways (24 ways, to be exact). By considering them in sorted order, we can eliminate the duplicate orders. Note that this does not mean the order with a < b < c < d gives a square. We might need to rearrange them as in a < b < d < c to get a square. You'll see how that works shortly.

Inside the loops, the find_solutions method calls get_square_points. That method determines whether four points can make a square and, if they can, it returns a list holding the points in an order that makes a square.

The following code shows the get_square_points method.

def get_square_points(point_a, point_b, point_c, point_d): ''' If these points make up a square, return a list holding them in an order that makes a square. If the points don't make up a square, return None. ''' # Get distances from point_a to the other points. distances = [ math.dist(point_a, point_b), math.dist(point_a, point_c), math.dist(point_a, point_d), ] # Zip the distances and their corresponding points. points = [point_b, point_c, point_d] zipped_lists = zip(distances, points) # Sort the zipped lists by the distances. sorted_lists = sorted(zipped_lists) # Unzip. distances, points = zip(*sorted_lists) # If the two smaller distances are not the same # (the side length), then this isn't a square. if not math.isclose(distances[0], distances[1]): return None # If the longer distance (the diagonal length) isn't # sqrt(2) times the side length, then this isn't a square. diagonal_length = math.sqrt(2) * distances[0] if not math.isclose(diagonal_length, distances[2]): return None # See if the distance between the farther point and # the two closer points equals the side length. distance02 = math.dist(points[0], points[2]) if not math.isclose(distance02, distances[0]): return None distance12 = math.dist(points[1], points[2]) if not math.isclose(distance12, distances[0]): return None # It's a square! Return the points in square order. return [point_a, points[0], points[2], points[1]]

The method first creates a list holding the distances between point_a and the other points. It zips that list with a list holding the other points and sorts the combined lists by the distances. It then unzips the result to get the distances in sorted order with the points list holding the corresponding points. For example, distances[2] holds the largest distance and that value is the distance between point_a and points[2].

Next, the code verifies that the distances to the two closer points are the same. If the points form a square, then that distance is the square's side length.

[The solution to the puzzle.] The distance from point_a to the farthest point must be the square's diagonal, so the method verifies that the distance is S * sqrt(2).

The code finishes by determining whether the farthest point is distance S from the other two points.

If the distances between point_a and the closer points are the same, and the distance between point_a and the farthest point is sqrt(2) times that distance, then this is a square.

The method returns a list of the points ordered to form the square.

After it finds the solutions, the program uses the same display code used by the earlier example Solve an equilateral triangle puzzle in Python. See that example for the details.

Download this example to see additional details.

Finally, you can see all of the solutions in the picture on the right.