6.5 C
New York
Saturday, March 2, 2024

Solving Martin’s Menace: A Computer Scientist’s Approach

Solving Martin’s Menace: A Computer Scientist’s Approach

Happy New Year! I’m excited to share with you a hobby project that I recently completed. A while back, a dear friend gifted me the Martin’s Menace puzzle. I initially spent several days trying to solve this dissection puzzle using only my brainpower, but I couldn’t crack it. It ended up on my shelf, gathering dust. However, just a few days ago, it struck me: While I may not excel at solving puzzles manually, my proficiency lies in using computers to solve problems. And here’s what I came up with.

SPOILER ALERT: This article reveals the solution to the puzzle, or at least give you some clues. I really encourage you to try to solve the puzzle without any help. It’s a Stewart Coffin puzzle (#217).

Martin’s Menace is a challenging dissection puzzle, designed to test spatial reasoning and problem-solving skills. It consists of four uniquely shaped pieces that must fit together in a rectangle that always seems to small!

We can see the pieces shaped like: “s”, “r”, “f”, “T”

I approached this problem like a classic search problem in artificial intelligence, exploring the state space to find the target solution using various strategies. Good Old Artificial Intelligence in this era of deep learning and LLM. Great!

In this context, it was crucial to:

  1. Define the state space and navigate it effectively.
  2. Detect when a solution has been found.

In artificial intelligence, “state space” refers to the set of all possible states or configurations that a system or problem can have. For Martin’s Menace puzzle, the state space includes every possible arrangement and orientation of the puzzle pieces.

My initial hypothesis was that orthogonal rotations (0, 90, 180, or 270 degrees) would suffice. This approach aimed to minimize holes or gaps in the puzzle. Similarly, I aligned the pieces along an imaginary grid, avoiding half-square alignments for the same reason. Thus, my state space and my search excluded solutions requiring different rotations or alignments.

I conceptualized various state space definitions:

First one: For each of the four puzzle pieces, I considered their <x, y> coordinates, orientations and side. Example: my f piece, at position <1,2> rotated 90 degrees and flipped. Move around the state space implies change some of this attributes: flip the piece, rotate or change the coordinates.

Second one: An incremental version that works piece by piece until complete all the board:

  • Starting with an empty board and adding the symmetrical “T” piece first. This piece is fixed in position <0,0> and all the other pieces will be around.
  • Placing the “f” piece in some position, orientation and side around the initial piece.
  • Repeating this process for the remaining pieces.

Example:

Board().add(piece_f, False, 90, 2, 4).add(piece_r, False, 0, 6, 6).add(piece_s, False, 0, 5, -3)

The size of this state space was considerable. Each piece could be placed in 2 sides, 4 orientations, and within a 10×10 grid, resulting in 800 different positions per piece. Therefore, exploring all possible combinations (800³ = 512,000,000) was a significant task, estimated to take around 60 hours on my computer using a single core.

Identifying a solution was initially challenging but the final approximation is simple. The key lay in calculating the minimal rectangle covering all the pieces. This involved computing the convex hull of all polygons and then determining the smallest enclosing rectangle.

It’s easy to calculate that using the minimum_rotated_rectangle function from the Shapely library.

If this rectangle fit within the available space, we’ve got it!.

I explored two options:

  1. Breadth-First algorithm, with custom implementation
  2. Genetics algorithm using DEAP library

Breadth-First Algorithm

This straightforward approach involved navigating the state space by adding one piece at a time, discarding invalid positions, and retaining unique solutions. This method yielded 76 candidate solutions with two pieces, 160 with three pieces, and eventually narrowed down to just two final solutions. It was surprisingly fast, taking less than a minute on a standard computer.

76 candidates with two pieces.
160 candidates with three pieces

And finally only two candidates for the final solution.

Genetic algorithm

I also experimented with genetic algorithms, particularly interested in the process and potential solutions they might uncover. By the way, I have to confess, I’ve always had a soft spot for genetic algorithms — they’re my favorite go-to method! There’s something fascinating about watching an AI mimic nature’s way of evolving solutions.

A genetic algorithm is a computational method that mimics natural evolution to solve complex problems. It starts with a random population of solutions, evaluates their effectiveness, and then iteratively produces new generations through processes akin to biological reproduction and mutation. Over successive generations, the algorithm selects and combines the most effective solutions, gradually evolving towards an optimal or near-optimal solution.

The key components defined were:

  • Individual: Consisting of the side, orientation, and position of each piece.
  • Fitness: Guided by the size of the enclosing rectangle. Smaller was better, with penalties for orthogonal rectangles, as they wouldn’t fit the Martin’s Menace dimensions.
  • Mutation: Random changes in parameters.
  • Crossover: Involving one piece from one parent and the rest from the other to generate offspring.

This approach revealed several near-solutions and the two final solutions already identified. Details of this implementation are also available on my GitHub.

This holiday season, I combined leisure with my love for technology by tackling puzzles with my computer. Delving into classic AI algorithms like Breadth-First Search and genetic algorithms was not only funny but also incredibly effective. In the end, I cracked the Martin’s Menace puzzle using the tools that define my professional expertise. This experience was a delightful blend of traditional pastime and modern tech, showcasing how a computer can be a powerful ally in solving even the most intricate challenges.

Happy 2024! Salut i intel·ligència!

Note on Solutions: I have chosen not to publish the exact solution out of respect for the puzzle’s integrity and to preserve the fun of solving it for others.

Source link

Latest stories