I was playing a PuzzelScript game involving sliding blocks that i just couldn’t solve. So I wrote an algorithm to solve it.
The algorithm used is a simple backtracking algorithm to find the optimal solution (the one using the fewest moves.) The user can create an arbitrary puzzle for solution, and then the algorithm attempts to find solutions, giving the user progress updates as it does. Once the solution is found it’s written out for the user, and the solution is animated.
- Challenge: The algorithm itself had to be written and optimised.
- Solution: Although the algorithm was relatively easy to write, there is still at least error, as it fails to find a solution for a problem in 12 steps, instead giving a solution in 13 steps. This error has yet to be found. By optimising a few steps, the algorithm was significantly improved. (Resolved, to be revisited)
- Challenge: The user should be able to create their own puzzles.
- Solution: This was achieved quite easily using my experience making tile based games. I used all the normal mouse event listeners. (Resolved)
- Challenge: The solution is animated.
- Solution: It turns out that animating the solution was relatively easy once the graphics had been made. The steps are handled using the normal
- Challenge: The algorithm should not max out the user’s CPU for more than 30 seconds.
- Solution: Using the user’s CPU for too long causes alerts to be raised in most browsers. The algorithm takes time to sleep as it progresses using the
window.setTimeoutmethod to free up the user’s CPU from time to time. (Resolved)
- Challenge: The progress is animated.
- Solution: I’ve used CSS based progress bars in the past before, but this is the first time I’d animated them. The only hard part here was estimating the number of possible combinations of \(n\) moves, and then scaling the bars accordingly. (Resolved)