My wife purchased a puzzle for our family, and her Aunt and Uncle that we’re staying with on vacation to do. The puzzle consists of nine square pieces each of which contain half of an image of a cat on each side. The completed puzzle is a 3×3 grid of the pieces where all of the cats match up. After an hour or so of trying to randomly try pieces and combinations, I decided to come up with a plan that would definitively solve the puzzle. I decided to break the problem down into a set of comparisons the computer could do – and write a program to solve the puzzle.

Before I get to far, yes, I was informed by my wife that this was cheating. However, I’m not sure I agree (feel free to provide your comments if you would like). I don’t agree because puzzle solving should be about using all of your skills to be able to create the solution – not just simple trial and error. If you believe I cheated in finding the answer, that’s OK. If you prefer to think, as I do, that what I did was find an ingenious way to solve the puzzle read on.

Since I’m not an expert in image recognition, I decided the first step was to inventory the pieces and convert the images into something easier to handle. I decided that each cat had a left and a right side of the image. Since there were four different cats I’d number them 1 (Black), 2 (Orange), 3 (Gray), and 4 (Tan). I would then label the left side of the cat as the A (or true) side and the right side of the cat as the B (or false) side. Then I could create a inventory of each piece with it’s numberic identifier for the piece (which I randomly assigned) and the number for the cat image on each side: 3b, 2a, 4b, 1a… With this conversion from physical objects into numbers in hand I was ready to create some classes and structures.

I decided at the most basic I was matching sides so I created a class with the Cat Number and Cat half variables. The cat number had to match and the cat half had to be opposite. Because of this I used a boolean for the cat half. I also created a method for the class called match, which took in another puzle side and returned a simple true-false to indicate whether the sides could be matched together. One key here is that I returned true of there wasn’t a piece on the other edge. I knew there wasn’t a piece because the cat number was zero.

I also needed a puzzle piece to contain the piece’s identifier and the sizes of the piece. I also created a puzzle placement class that considered the orientation of the piece – since pieces could be rotated you didn’t know which side should be up. Finally I created a puzzle solution class to hold attempted solutions. The puzzle solution class had a method to return whether two solutions matched. This was used to prevent solutions from being tried multiple times by the program.

The main code of the program consisted of some lines to initialize variables, followed by a set of nested loops. The outer loop was a solutions loop where I recorded each tested solution. Inside of that I had loops for x and y positioning and inside of that pieces and inside of that orientation. Through these loops I’d test a piece at a time in each orientation to see if I could get it to match on all four sides. One key here was my array of positions was actually five by five and not three by three. Why? I kept a set of empty positions all around the pieces so that I didn’t have to worry about running into array bounds issues. It was wasteful of memory to be sure – but it’s efficient from a coding perspective and given this was quite literally throw away code, it seemd like a reasonable thing.

After working out some of the logic and a few minor logic bugs I ended up with a program that tried 283 solutions before finally settling on and displaying the answer on how to solve the puzzle to me. I should say that the answer was displayed instantaneously – at least to me it was instantaneously. I’m sure there were some number of milliseconds involved but to me they weren’t even measurable. I tested the solution on the real puzzle and it worked.

I ended up having about an hour in the code – and I’m certain that solving the puzzle by hand would have taken much longer than this given the complexity of the problem so I was happy with my puzzle solution.

Clearly you can’t use this technique to solving every puzzle. The typical jigsaw puzzle doesn’t lend itself quite as nicely to this sort of problem – but it was a fun exercise to convert a real world puzzle into an algorithmic one that the computer could solve.

The completed puzzle looks like this:

If you want to look at the code it’s available here.