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

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

Peteron Apr 5, 2009Hi,

How many numbers can you reduce from the grid until it won’t have a unique solution?

By

Itay Merchavon Nov 22, 2010Difficult to say since I haven’t tested it

By

Jani Hartikainenon Nov 23, 2010try chewdoku on http://twasack.tripod.com/index.htm

By

ddon Feb 21, 2011Thanks 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 Youngon Jun 5, 2011the code u wrote in _miniGridValid function is realy cool and professional.

By

nidoon Oct 20, 2011Bummer! This routine has bugs :-/

By

Sylviaon Mar 20, 2012Feel free to point out any issues you have with it. You would be the first, though.

By

Jani Hartikainenon Mar 21, 2012Hi 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 Dubalon Apr 4, 2012Pranav, 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 Hartikainenon Apr 4, 2012Very 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

Ericon Jul 25, 2012Here 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

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

By

Yael Froehleon Sep 2, 2013