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 equilateral triangle puzzle, and explains how to solve them. (Manually, not necessarily with a program.)

Title: Solve an equilateral triangle puzzle in Python

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

The goal of the equilateral triangle puzzle is to figure out how many equilateral triangles you can make by connecting triples of the points shown in the picture.

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

There are two fairly interesting pieces to the program: the part that finds the solutions and the part that displays them.

Finding Solutions

To find the solutions, the program simply enumerates every possible triple of points and determines whether they form an equilateral triangle. Here's the code.

def find_solutions(points): '''Find the solutions.''' solutions = [] for i in range(len(points)): for j in range(i + 1, len(points)): dx_ij = points[j][0] - points[i][0] dy_ij = points[j][1] - points[i][1] dist_ij = math.sqrt(dx_ij * dx_ij + dy_ij * dy_ij) for k in range(j + 1, len(points)): dx_jk = points[k][0] - points[j][0] dy_jk = points[k][1] - points[j][1] dist_jk = math.sqrt(dx_jk * dx_jk + dy_jk * dy_jk) if math.isclose(dist_ij, dist_jk): dx_ki = points[i][0] - points[k][0] dy_ki = points[i][1] - points[k][1] dist_ki = math.sqrt(dx_ki * dx_ki + dy_ki * dy_ki) if math.isclose(dist_jk, dist_ki): # This is a solution. solutions.append((points[i], points[j], points[k])) return solutions

This method makes variable i loop through the point. For each i value, it makes j loop through the later points. And for each j value, it makes k loop through the remaining points.

You may notice that this means i < j < k, so you might wonder about other possible combinations of points. There are other combinations that make triangles, but they will be duplicates of the ones where i < j < k. For example, if points 6, 2, and 8 form a triangle, then those same points in the order 2, 6, and 8 form the same triangle. Ensuring that i < j < k gives us all of the triangles without duplicates.

Anyway, for each i, j, and k, the code checks whether the distances between each pair of the three are the same. If the distances are the same, then the triangle is equilateral and the code adds the points to the solutions list.

After it finishes checking each triple, the method returns the solutions that it found.

Displaying Solutions

After it finds the solutions, the program calls the following draw method to display them.

def draw(self): '''Draw the points and solutions.''' # Delete any previous drawing objects. self.canvas.delete(tk.ALL) self.current_solution = None # Draw the points. RADIUS = 5 COLOR = 'blue' for point in self.points: self.canvas.create_oval( point[0] - RADIUS, point[1] - RADIUS, point[0] + RADIUS, point[1] + RADIUS, fill=COLOR) # Draw the solutions starting with the first one. self.DELAY_MS = 250 self.window.after(self.DELAY_MS, self.draw_next_solution, 0)

This code clears the program's Canvas widget and then loops through the points drawing ovals for each.

If then uses the after methods to wait 500 milliseconds before executing the following draw_next_solution method.

def draw_next_solution(self, solution_number): '''Draw solution number solution_number.''' # Delete previous solutions. if self.current_solution is not None: self.canvas.delete(self.current_solution) # See if we've drawn them all. if solution_number == len(self.solutions): # We're done. Draw them all. for solution in self.solutions: self.draw_solution(solution) self.num_solutions_label['text'] = f'{len(self.solutions)} solutions' else: # Draw the next solution. self.draw_solution(self.solutions[solution_number]) # Wait and then draw the net solution. self.window.after(self.DELAY_MS, self.draw_next_solution, solution_number + 1)

This code checks self.current_solution, which holds a reference to the most recently drawn solution. If that value is not None, the program removes that triangle.

Next, the code checks the triangle number to see if we have already drawn all of the triangles. If we have, the code loops through all of the solutions and calls draw_solution (described next) to draw them all.

[The solution to the puzzle.] Otherwise, if we have not already drawn all of the solutions, the code calls draw_solution to draw the next solution. It then calls after to wait 500 milliseconds and then invoke the draw_next_solution method again to draw the next solution.

The following code shows the draw_solution method.

def draw_solution(self, solution): self.current_solution = self.canvas.create_polygon( solution, outline='red', fill='')

This method uses the Canvas widget's create_polygon method to draw the solution, saving the returned identifier so the draw_next_solution method can delete the triangle later.

Download the example to see additional details.

Oh, yeah. You can see all of the solutions in the picture on the right.