Generating Sudoku puzzles using JavaScript
November 29, 2008 – 2:11 pm Tags: Games, JavaScriptWhile 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.
Subscribe to my RSS feed
12 Responses to “Generating Sudoku puzzles using JavaScript”
Hi Jani,
I’ve spent ages trying to come up with a simple way of creating Sudoku grids – in the end I used the “interesting approach” that you refer to in my game “Magicama” and this worked well enough for my purposes.
But the above algorithm blew me away – so simple and elegant – and so fast!
Great stuff!
If only there was a simple way to turn a solution grid into a good puzzle!
Peter
By Peter on Apr 5, 2009
Hi,
How many numbers can you reduce from the grid until it won’t have a unique solution?
By Itay Merchav on Nov 22, 2010
Difficult to say since I haven’t tested it
By Jani Hartikainen on Nov 23, 2010
try chewdoku on http://twasack.tripod.com/index.htm
By dd on Feb 21, 2011
Thanks for your efforts, but actually it doesn’t work!
Because your code has a dependency on
App.Utils.arrayContains()
I guessed what this missing function does, and rolled my own, but maybe you should either provide the dependent code, as a seperate download, or inline it somehow, or simply warn your readers about it.
Thanks!
By Brennan Young on Jun 5, 2011
the code u wrote in _miniGridValid function is realy cool and professional.
By nido on Oct 20, 2011
Bummer! This routine has bugs :-/
By Sylvia on Mar 20, 2012
Feel free to point out any issues you have with it. You would be the first, though.
By Jani Hartikainen on Mar 21, 2012
Hi Jani, You have written a seriously professional code, but there is some error, I suppose. The script shows error on “App.Utils.arrayContains(number, value)”.
I need this urgent. Can you please fix it as soon as possible or just give me an insight on the function so that I can code it myself.
By Pranav Dubal on Apr 4, 2012
Pranav, yeah I sadly forgot to include that. It’s just an utility function which checks if an array contains a value and returns true or false. You could probably use Array indexOf or something.
By Jani Hartikainen on Apr 4, 2012
Very nice and concise sudoku generator. I agree with nido, the miniGridValid function really is brilliant.
The issue I’m running into is that I generate a board, cull the cells, but sometimes the culled board can be solved in multiple ways. This invalidates comparing a generated board to a culled and human populated board.
I suppose you could do a validity check on each number entry, but what if I wanted to give hints?
Is there a way to implement culling so that it retains the one solution only rule?
By Eric on Jul 25, 2012
Here is a brute force algorithm I’m using to check if the board has a unique solution or not. This isn’t the most efficient, but it works for my purposes:
/**
* Runs board through a series of tests to ensure that it only has one solution
* @method
* @private
*/
_testUniqueness: function ()
{
// Find untouched location with most information
var rp = 0, cp = 0;
var Mp = null;
var cMp = 10;
for (var r = 0; r < 9; r++) {
for (var c = 0; c < 9; c++) {
// Is this spot unused?
if (this.culledBoard[r][c] == 0) {
// Set M of possible solutions
var M = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var cM = 0;
// Remove used numbers in the vertical direction
for (var a = 0; a < 9; a++) {
M[this.culledBoard[r][a]] = 0;
}
// Remove used numbers in the horizontal direction
for (var b = 0; b < 9; b++) {
M[this.culledBoard[b][c]] = 0;
}
// Remove used numbers in the region
var regionLimits = this.getRegionLocation(r, c);
for (var x = regionLimits.start.r; x < regionLimits.end.r; x++) {
for (var y = regionLimits.start.c; y < regionLimits.end.c; y++) {
M[this.culledBoard[x][y]] = 0;
}
}
// Calculate cardinality of M
for (var d = 1; d < 10; d++) {
cM += M[d] == 0 ? 0 : 1;
}
// Is there more information in this spot than in the best yet?
if (cM < cMp) {
cMp = cM;
Mp = M;
rp = r;
cp = c;
}
}
}
}
// Finished?
if (cMp == 10) {
return sudokuUniqueResult.unique;
}
// Couldn't find a solution?
if (cMp == 0) {
return sudokuUniqueResult.noSolution;
}
// Try elements
var success = 0;
for (var i = 1; i 1) {
return sudokuUniqueResult.notUnique;
}
}
}
// Restore to original state.
this.culledBoard[rp][cp] = 0;
switch (success) {
case 0:
return sudokuUniqueResult.noSolution;
case 1:
return sudokuUniqueResult.unique;
default:
// Won’t happen, not unique
return sudokuUniqueResult.notUnique;
}
},
By Eric on Aug 1, 2012