XOR Media

Coding, Operations, Etc.

Puzzle Solver

Posted on Fri 09 January 2015 by

Backstory

Final Puzzle Solution

My brother got me a pretty cool puzzle for Christmas which claims to have "Over 300,000 wrong ways to assemble the pieces, but only One right way!". The only hint/instructions are that the final solution will be a 3x3 square with six points and six holes on the outside.

Both my wife and I played around with solving it for a decent amount of time each and together some, probably a total of a couple hours. We both could get 8 of the nine pieces placed (multiple times) but could never find a setup that would fit the final piece. In talking about the puzzle we discussed the brute force approach to solving it, trying every piece in every possible place and rotation, ...

I realized that it would be pretty cool to actual code up a solution. So I took the piece and threw them all out in the same orientation on the kitchen floor and took a picture of them. I then cut them up with gimp, and used convert to generate the 90, 180, and 270 rotated version. After that it was a bit of html and css, and a decent amount of hacking around in js (thought it would be the best way to do it so that others could see/watch.) I started off making things more complicated than they needed to be trying to keep track of what'd be placed where. After that wrong turn I backtracked and realized that it would be much cleaner and simpler to just have the pieces know when they've been placed and try to place them again and just ask if that's possible.

After that change and getting rid of the rest of the wrong-turn it probably took about 30m, maybe an hour to finish things up and what you see to the right is the result, and the live version is below. The example is running at 256 tries a second (if you're browser is up to it.)

I was fully expecting the solver to run for a couple hours trying all of the possibilities, but by random chance I managed to lay out the pieces, cut them up, and enter them in to the code in an order that gets to the correct answer after only 3554 placements. So what could of been hours takes less than a minute.

It was thrown together as quickly and is in the style of a hack rather than a good/clean solution, but I'm reasonably happy with it. Let me know what you think.

Ticks: 0
In misc, tagged: algorithms, coding, examples, and javascript.

About the Author

Ross McFarland Ross McFarland | | |

Ross is a 13 year veteran of the software industry with experience spanning low-level signal processing, web and mobile user interfaces, and high-scale distributed web services including Amazon.com's Digital Media Group. He has made extensive contributions to open source highlighted by his time as a primary maintainer of Gtk2-Perl and author of requests-futures and python-asynchttp librarys. (more)


Comments