This is a Sudoku puzzle generator and solver. This program provides two generation algorithms, a solver and methods to update and check the state of the puzzle. I had found a JavaScript Sudoku at https://www.dhtmlgoodies.com/scripts/game_sudoku/game_sudoku.html which I thought was pretty cool, however, it didn’t create very good puzzles. Most had more than one solution and if you didn’t find the solution it chose as a the final solution, you would never finish the game. I started thinking about how you would actually create a working Sudoku puzzle. This is my first attempt. 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. The game can be found here. The source contains very detailed comments describing how the algorithm works. The source can be viewed here. Have fun. Send any comments, bugs, contributions to djrager@fourthwoods.com
Useful resources:
- JavaScript: The Good Parts
- JavaScript & jQuery: The Missing Manual
- JavaScript, A Beginner’s Guide, Third Edition (Beginner’s Guide (Osborne Mcgraw Hill))
- JavaScript Patterns
]]>