28 Mar 2021 - Stephen Parsons
Sometime within the last few Christmases, my soon-to-be mother-in-law gave me a wooden puzzle I was never able to solve. I’ve been gifted a number of puzzles and keep a growing collection; especially before there was a pandemic and we went a year without any visitors, I would leave them by the couch for my friends to idly play with while hanging out. This one stumped myself and all visiting friends and family for some time:
The idea is pretty simple, and all one has to do is fit the four pieces flat inside the frame. Simple, however, does not mean easy. The large state space (there are many possible combinations to try) and uninformed search (I can’t very well tell which partial combinations are any better than the others, so I’m just guessing blindly) make this one a challenge, at least for me. Some other wooden puzzles offer more of a sense of progress, and you can sort of tell when you are working in the right direction. Not so here. “Why,” I would ask myself, “am I doing this? Isn’t this sort of thing what computers are for?”
So around a year ago that’s what I did, and I hacked together a horrible Python script to solve it. Here’s the program doing its thing:
More recently it occurred to me that the Stephen of a year ago had completely forgotten his manners and his basic algorithms training. The puzzle states can be explored using any off the shelf search algorithm, there is no need to get fancy. I forgot this entirely for my first solution, which resembled depth first search but worse, and involved much global state and pain. That solution is deliberately omitted.
This morning I cleaned things up so it works with a vanilla depth first search. Of course it solves the puzzle like before:
But it does so in a way that gives me less anxiety. I also used this as an excuse to play with Python’s dataclasses, which was nice. I think I will use them again.
The full script is here. Alternatively you can run it in this Colab notebook to get a feel for it, though it will likely time out before finding a solution, which takes 28 minutes on my laptop.