Our "four-color map theorem" puzzle is a bit hard to make, and so it's been out-of-stock for years (thanks Stephanie for finally getting this made again!)
I've personally done it about 20 times, it's a good puzzle for passing out with the coffee after dinner with friends, and letting people pass the pieces around until they find a connection.
The four-color map theorem says that no matter how complicated your map, you only need 4 different colors to color it, and you can color it so that no two adjacent countries get the same color.
As a kid, I spent hours drawing maps of convoluted mythical lands, trying to break the four-color map theorem.
Our four-color map puzzle is delightfully convoluted, each piece a "country," and yet the four color theorem still holds - no piece connects to a piece of its same color!
It's one thing to say "there exists a way to color a map with just 4 colors" and it's another thing to actually take a crazy map and find a way to color it with just four colors.
Just imagine you started coloring our 67 piece "map" - for the first piece you have 4 color options, say you choose Blue. And you have 4 color options for the next piece, but you can't use the same color as the first piece, so really you have just 3 choices, say you choose Red. Now say the next piece touches both your Blue and Red piece, so you color it Green. Now say the 4th piece you go to color also touches all three of those pieces so you color it Yellow. Now you look at your 5th piece and depending on what it touches, you only have a couple color options... If you make a bad choice when you color the 8th piece, you can easily end up with no colors that work for the 9th piece!
So, this is exactly the sort of problem best-solved by computers, and in fact once we had the 67 pieces, I wrote a custom depth-first search tree in Python (a computer language) to explore all possible colorings for the 67 pieces, and stop as soon as it found a choice of 67 colors that satisfied the map. Only took the darn computer about 10 minutes to find a solution!
We had originally planned to come out with a much larger version of this puzzle, maybe 150-300 pieces, also satisfying the four color map theorem, but never got around to it. If this one sells well, we'll see what we can do about that.