Yesterday, during an interview, I was asked how to programatically solve a sliding puzzle. Given a mixed up puzzle, solve it and output a list of moves that would take you to the solution. After working it through for a bit we seemed to have a decent approach and moved on to other questions and interview stuff. However, thinking about it later in the day, I realized we missed something. I enjoy puzzles and programming, so last night I decided to look at it again and actually write the program.

When first posed, my first thought was too complex to write. I wanted to, given the current possible moves, decide which one would take me closer to the solution. My interviewer was kind enough to point out that this gets tricky quickly and wasn’t a very good idea. It’s true. I have played with these types of puzzles before, but it was doubtful that I could remember the strategy in the moment. Let alone a strategy that could be implemented in code. With some coaxing “How many possible positions are there?” and something like “Instead of a smart monkey, how about a monkey named Brute.” Yes, of course, it would be easy for a computer to try all the moves until the solution was reached. And this is where we missed a step, sorta.

The brute force method would be to start with the original, mixed up, state of the puzzle and make one of the available moves. Repeat until solved. If there is ever more than one available move just take the first because you are going to try the others later. The problem is that you could move A to B in the first move and then back in the second step. This would continue until the end of time. We never really got into the implementation of choosing a move so this it isn’t fair to say that we missed this. More like we never got to it. I did when I was working on the code.

When faced with choosing a move, I randomly pick one of the available moves. This works for the puzzles I tried it with. After chewing on the puzzle for a while, I get it back into the state it started in. Cool. Unlike the original problem I am not tracking the moves taken to get back to the solved state. I may work on that at a later date.

A slightly smarter monkey?

I posted the code on github if you want to take a look. I’ve already had some ideas about how to improve it. Looking at the output of solving a small puzzle, I noticed that it was one move away in a few steps, but the random move picker picked the wrong move. So one possibility, instead of randomly picking a move, would be to try each of the possible moves in turn and checking if it solves the puzzle. If it doesn’t “undo” that move and the others. If none of them solve the puzzle, go back to picking one randomly. This would slow down the selection process but might speed up the solution.

Larger puzzles

I have only tested with 2×2, 2×3 and 3×3 puzzles so far. (I’m going to let the 4×4 run while I go run some errands.) It’s no surprise that as the size of the puzzle increases, the amount of time needed to solve it goes up. It would be interesting to run the same puzzle a bunch of times and compare solution times and number of moves needed to get to the solution between different move picking strategies. Okay, I might be spending more time on this than I should. I had a lot of fun with it though!