Being a programmer, I decided it would be more fun to program my computer to solve the puzzle. I spent a couple of hours on it, and came up with a nice result. I'll share the result below, along with some observations about the program and the puzzle.
First, here's a link to the puzzle: http://www.palmettopuzzleworks.net/
You can buy it directly through Etsy for $20.
Before I delve into my program, let me start by suggesting that this might make a great programming assignment. It's a very well-defined problem, but with a number of subtleties to watch out for.
So let me show you my solution. My intuition was that this would be a computationally complex problem, and it looked like a good fit regardless, so my language of choice was C.
The first thing to do is define the data structures. I've found that in the vast majority of problems, the data structures drive the code. If you have the wrong data structures, you'll never get a good solution, but with the right data structures, the code mostly flows into place.
As you can see in the picture, the board is an 11x11 grid with some spaces filled in. That makes the board an easy two-dimensional array. The largest piece fits in a 4x5 grid, so I created a three-dimensional array for the pieces initialized to a 1 for the spots that are filled and a 0 for the squares not occupied. Thinking ahead, I'm going to have to rotate each piece, so I need to use a square for each piece, not just a rectangle, so each piece is a 5x5 grid.
Initializing the grid is pretty simple: a zero represents an open space, a number indicates a piece (1 through 9), and another constant represents the border (10). Because the border is more filled than open, the code fills the borders, then opens up the spaces where a piece can intrude.
Now here we come to the key trick to make the whole thing work. I have to try each piece in four different rotations. If I rotate the pieces on the fly, the program will be spending most of its time doing rotations. That's not a good idea for something that is already likely to be quite computationally intensive. So why not save the work and just do it once? This raises one subtlety to the problem: The pieces all fit in a 5x5 grid, but have at least one row or column empty. The solving code will want to assume that the top row and left column are non-empty, so each rotation has to also shift to make that happen. With that explained, there's nothing particularly fancy about the code, though I'll admit that on the first run, it mangled the pieces by doing some reflections as well as rotations.
Before writing the code to try all the combinations and find the solution, I need to be able to display the board. I also need to be able to display the pieces to check that I've coded and rotated them correctly. This is a place where spending a few minutes extra to have nice readable output can save a lot of time in understanding the results. Using a graphics toolkit or generating HTML would be overkill for this problem. Simple printing to the console would be fine, but tossing in some ANSI color codes to make the pieces easier to visualize would be well worth the effort. Fortunately, I have a handy set of ANSI color code defines:
So using those defines to display the grid and the pieces is fairly straightforward. You'll notice that I take advantage of C's string concatenation--any two strings separated only by whitespace are treated as a single string.
With the above code, I have all that is needed to display the pre-rotated pieces (which proved vital for debugging mangled rotations) and the game board with any pieces placed in it. Starting out, it looks like:
So the the code to actually go through the placements feels anticlimactic at this point. It simply marches through the puzzle, trying every possible combination in much the way I would do if I were doing an exhaustive search by hand. Here's the complete program:
Now much to my surprise, once I had debugged it, it ran quite fast. I had guessed that it might run for hours before finding the solution, but it ran to completion in under a minute. The biggest surprise was that it found not one, but eight solutions! I shared my results with the creator of the puzzle. He said he had also used a computer to verify that there was only one solution, but apparently his program had a bug. He has made a slight change to the puzzle, so if you buy it now, it will have one unique solution.
In case you're interested in buying and playing with the puzzle yourself, I won't spoil it by posting the solution here. It's simple enough to run the program if you want to see them.
And a note on copyright: While I hold the copyright on all my posts, including the above code, in my opinion, the ANSI color code defines are simple and obvious enough that they can hardly be considered copyrightable, so feel free to use them.