My "One Tough Puzzle" JavaScript Brute Force Solution

My "One Tough Puzzle" JavaScript Brute Force Solution

Posted by Brad Wood
Sep 30, 2012 04:20:00 UTC
So, I've been sitting on this for months (because I'm lazy) and decided it's finally time to post it. My mother-in-law visited a while back and brought a puzzle for the kids to play with. It's called "One Tough Puzzle". It claims to have "more the 300,000 wrong ways, but only one right way to assemble it." Well, after fiddling with it for a while, I did what any code-blooded hacker would do and wrote some JavaScript to brute force solve it.

The Setup

The puzzle comes with 9 large, red pieces whose interlocks are in the shape of hearts, spades, diamonds, and clubs. It has no picture-- just solid red pieces with no outside border. At first solving it will seem easy until you get to the last couple pieces which don't fit and you must start over.

The Plan

I haven't looked in several months but at the time, the only code-related solvers I found on the Internet were text-based. CFML is my language of choice, but I wanted to build a visual solver that ran in the browser so you could actually see the puzzle being solved. I wrote a collection of Java Script classes to represent the game, the table, the person, and each piece. The code starts with the top left piece and resursivley tries every single combination of pieces and rotations of those pieces. (Each piece can be turned 4 different directions) When the code hits a dead end, it backs up and tries another piece. Once all 9 pieces are in place and matching, it's finished.

The Rendering Problem

So the code runs fast-- too fast actually. I tested with IE (slowest by FAR), FireFox (fastest), and Chrome (really really close behind FireFox). Typically the browser was able to find the winning combination in only a few milliseconds. The first issue was that the solving happened too quickly to really enjoy. The second problem is that when innerHTML() is called a bunch of times in a row, every browser would completely lock up for about a minute and then finally display the final HTML. Not cool, bro. To slow down the rendering and ensure that every juicy frame was shown, I appended the HTML of each step to an array, then set up a JavaScript timeout on the page to render a frame every few milliseconds.

The Code

Here is a zip file with the working sample if you want to play around with it. For the sake of keeping it simple, I used no JavaScript frameworks (sorry, jQuery lovers).

Download sample code

The Solver

For you for souls who crawled in here from Google just looking for some relief from this relentless puzzle, I won't keep you any longer. Hit the solve button to watch my code solve the puzzle. When it's done, if you hold down the shift key, and hold your math homework up to the screen, it will solve that too.

 


Aaron West

Brad, this is really, really awesome. Thanks for taking the time to write this up and share your work. I love puzzles and code so this is a nice intersection of the two. I've also been wanting to create a maze generator for a while as my son enjoys them. I can see some similarities between your puzzle work and what I hope to one day create. Have a great new year!

SK Bhardwaj

that was really interesting .. :)

Site Updates

Entry Comments

Entries Search