Archive for February, 2011
The puzzle is generated using the solver to solve an empty Sudoku board. It implements a backtracking algorithm in which it randomly selects numbers to try in each cell. It starts with the first cell and picks a random number. If the number works in the cell, it recursively chooses the next cell and starts again. If all the numbers for a cell have been tried and none work, a number chosen for a previous cell cannot be part of the solution so we have to back up to the last cell and choose another number. If all the numbers for that cell have also been tried, we back up again. This continues until a value is chosen for all 81 cells. (The actual implementation is pretty much what is described here though it does use some optimizations and tricks so it isn’t too painfully slow. If you’re interested check out the source which is heavily commented.)
Once the board is filled in, values are removed until no more values can be removed without creating a puzzle with more than one solution. Actually, Medium and Hard are guaranteed to have only a single solution. Easy uses a naive algorithm similar to that used at the dhtmlgoodies.com link above which may have more than one solution. Don’t worry though, if you find a valid solution the game will finish.
Have fun. Send any comments, bugs, contributions to firstname.lastname@example.org
Update: This script has been updated as of this newer article.
So, I thought it would be cool to create a program for my daughter that would generate mazes that she could print out and solve. Originally I was going to create a Windows program but I didn’t really feel like dealing with the windows GDI and printer quirks. Luckily for me, and all the other web developers in the world, web browsers happen to have printer support built in!
Fourth Woods Blog
- Culture and Copyright (1)
- Database (5)
- Emulation (1)
- Programming (40)
- Tips and Tricks (22)
- Uncategorized (2)