Sudoku in JavaScript

Author: David Rager
Date: February 5, 2011

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:

]]>

Maze Generation script

Author: David Rager
Date: February 3, 2011

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! I created a random maze generator in javascript, based on a modified version of Kruskal’s algorithm. This code is modeled roughly on the fast_maze program that can be found at https://nehe.gamedev.net written by smart_idiot. When I wanted to learn several years ago how maze generators worked, this was the algorithm learned. The maze generator requires a browser that supports HTML 5 and the ‘canvas’ element. This is basically any modern browser except Internet Explorer. (IE users can try to use excanvas.js but you’re on your own.) You can try it out here. You can also download the javascript for it here. Have fun.