Generating Sudoku puzzles using JavaScript

November 29, 2008 – 2:11 pm Tags: ,

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

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.

1. 13 Responses to “Generating Sudoku puzzles using JavaScript”

2. 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

3. 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

4. Difficult to say since I haven’t tested it

5. try chewdoku on http://twasack.tripod.com/index.htm

By dd on Feb 21, 2011

6. 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

7. the code u wrote in _miniGridValid function is realy cool and professional.

By nido on Oct 20, 2011

8. Bummer! This routine has bugs :-/

By Sylvia on Mar 20, 2012

9. Feel free to point out any issues you have with it. You would be the first, though.

10. 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

11. 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.

12. 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

13. 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

14. I visit daily a few web sites and blogs to read articles, except this blog gives feature based posts.|

You can use some HTML (a, em, strong, etc.). If you want to post code, use <pre lang="PHP">code here</pre> (you can replace PHP with the language you are posting)