While I’m not the biggest fan of Sudoku puzzles, I wanted to make a sudoku widget for the Opera x-widgets challenge. This required me to study the algorithms used for generating sudokus, which was actually a quite interesting challenge.
While there are some examples of generating sudokus online, such as this interesting approach, it seems there’s only one “true” way: Using a backtracking algorithm.
There were also some examples of backtracking, but I found them confusing and not easily usable as-is, so I decided to write my own generator script, that anyone could just take and use in their own projects.
The backtracking algorithm
The basic idea of the algorithm is as follows>
- Try all available numbers in the cell
- Found a possible number? Put it there and continue to next
- No possibilities? Go back one cell to try other numbers there
Succesfully implemented, this algorith can do very quick work of generating a full 81 cell sudoku puzzle. Even on my phone, which is by no means a very powerful PC, it runs so fast you won’t even notice it when generating a puzzle.
The generator must also be able to determine whether a number can be placed in the cell or not. Sudoku rules say that each horizontal row and vertical column in the puzzle must have numbers from 1 to 9 and exactly once. There’s also 9 3×3 grids in the big 9×9 grid, which all must contain numbers from 1 to 9.
The implementation
You can download the full source from the code-repo.
The implementation is divided into two classes: CU.Sudoku and CU.sudoku.Grid.
The Sudoku class is a helper class used when generating grids, and it has methods generate and cull, which generate a new puzzle and clear items from it respectively.
//Generate a complete puzzle var grid = CU.Sudoku.generate(); //Clear 60 cells from the puzzle CU.Sudoku.cull(grid, 60); |
The Grid class represents the actual 9×9 grid of numbers. It has methods for handling values in cells, checking for validity and outputting the grid in an array.
//grid is the culled grid from the previous snippet //set value in column 5, row 8 to 2 grid.setValue(5, 8, 2); //Check if column 5, row 8 has a value that doesn't conflict alert( grid.cellConflicts(5, 8) ); |
Using the methods provided, it’s easy to build a sudoku game around these classes. You only need to worry about the user interface implementation. For example, you can check out my sudoku widget, which uses these classes as the base.
My implementation probably isn’t perfect, but it works quite well, and should be easy to understand and use. Feel free to point out any areas of improvement or other.