13,868,406 members
alternative version

#### Stats

55.9K views
73 bookmarked
Posted 30 Nov 2011
Licenced CPOL

# HTML5 Sudoku Solver

, 16 Dec 2011
An HTML5 JavaScript Sudoku solver.

## Introduction

This article describes an HTML5 Sudoku solver. The entire program is in one HTML file and it uses JavaScript and the new HTML5 `Canvas` element. This is my third article about HTML5/JavaScript, each article being more complicated than the previous and really just a series of learning steps for myself.

## Background

I don't think I really need to say much about Sudoku except that it is a very popular and addictive game and there have been many articles published about Sudoku solvers in various languages. My wife actually got me interested in the game - I learned the basic rules for solving and quickly decided that I was less interested in mechanically working through various solving techniques and more interested in coding up a solver to do it for me - particularly when I hit a hard problem!

A screenshot of the application below shows the main elements. The main element is the board which shows the 9 x 9 grid divided into 3 x 3 "squares". The "givens" are in a darker font while the user entered digits are lighter. Each cell on the board has the allowed values shown in the background in a very light font. "Singles" are shown in a red font - note singles is a standard Sudoku term and refers to a case where an allowed value is the only possible one.

The current cell has a pink background and it can be changed by using the mouse to click in a cell or using the keyboard arrow keys. The user enters a digit by just typing the digit and clears it by typing the 0 digit.

Below the board is a text box containing the serial format of the board data. This is a common format used by Sudoku programs and is simply each digit on the board in order from top to bottom and left to right with empty cells represented by a ".". As the user enters new digits, the serial format is automatically updated, and if the Load button is pressed, then whatever text is in the text box is loaded into the board.

All the buttons are located to the right of the board and are as follows:

• Clear - basically clears every cell including givens.
• Load - already mentioned loads the serial format, but one other point to make is that if you are manually entering a problem, the digits will appear as user entered, but by clicking the Load button, it will "convert" them to givens. It is important to distinguish user values from givens because givens can't be modified. Also, when the Reset button is pressed, all cells except the givens are cleared.
• Reset - clears all cells except givens.
• Accept -converts all "singles" into an actual value.
• Hint - enters the answer to the current cell in that cell. It gets the answer from the current board hence if the board is already incorrect, no hint will be given.
• Undo - undoes the last digit entered or other user actions such as Accept or Solve. It is implemented using a stack so records can undo an unlimited number of actions. A Load, Reset, or Clear empties the undo stack.
• Solve - solves the entire problem from the current position. This may not give the solution if values already entered are incorrect. After solving, the status is displayed below the buttons and the time taken to solve is displayed below the serial format text box.

Below the buttons are two check boxes, one to enable display of the allowed values and another to enable highlighting singles in red. Note: some Sudoku players prefer not to get assistance when solving, which is why you would use these options.

## Using the Code

The code for the solver uses the most basic techniques for solving - first scan all the "givens" and determine which digits are allowed in which cells. If only one allowed value exists, then it is a "naked" single. Because each digit must occur exactly once in each row, column, or square, we then scan each of these and if an allowed value only occurs once, then it is a "hidden" single. Singles values are not necessarily correct - the board can get to a state where a given digit is the only digit in two cells in the same row, col, etc., so we test whether the value is valid before applying it.

Applying the above techniques will only get you so far. There are in fact many other manual techniques, e.g., naked and hidden doubles, triples, quads, X-wing, etc. We don't use any of these but simply adopt a simple trial and error or decision tree approach. So at a given point, we find a cell with the least number of alloweds, then try each one in turn. If successful with that cell, then we advance further up the decision tree, regressing when the board becomes invalid and we have run out of alternatives.

Well that's the algorithm in basic terms. The model code was implemented in four classes as follows:

• `AllowedValues` - this stores the allowed values for a cell. It is implemented in a bit mask, i.e., if the digit N is allowed, then bit N in an integer is 1 while 0 is not allowed. This provides efficient storage of alloweds (which speeds up making copies of the board as required by the decision tree code) and simplifies combining alloweds using simple bitwise OR operations or removing them by masking.
• `Cell` - this represents one of the 9 x 9 locations on the board. It contains the `AllowedValues` for the cell, the given value, and the user entered value.
• `Location` - this has two fields: row and column. It is used to simplify calculations and provides useful functions like a list of locations of sibling cells in rows, columns, and squares.
• `Board` - contains 9 x 9 `Cell` instances. It implements most of the solving related code such as calculating allowed values, singles, and solving.

There is a lot of code to cover so I will just mention one key piece of code which is the calculation of the allowed values shown below.

```//
Board.prototype.updateAllowed = function () {
// Called whenever the user sets a value or via auto solve
// Updates the allowed values for each cell based on existing digits
// entered in a cell's row, col or square
var cols = new Array(BoardSize);
var rows = new Array(BoardSize);
var squares = new Array(BoardSize);

// First aggregate assigned values to rows, cols, squares
var locs = Location.grid();
for (var i = 0; i < locs.length; i++) {
var loc = locs[i];
// Disallow for all cells in this row
rows[loc.row] |= contains;
cols[loc.col] |= contains;
squares[loc.getSquare()] |= contains;
}

// For each cell, aggregate the values already set in that row, col and square.
// Since the aggregate is a bitmask, the bitwise inverse
// of that is therefore the allowed values.
this._isValid = true;
this._isSolved = true;
for (var i = 0; i < locs.length; i++) {
var loc = locs[i];
// Set allowed values
var contains = rows[loc.row] | cols[loc.col] | squares[loc.getSquare()];
var cell = this.getCell(loc);
// set allowed values to what values are not
// already set in this row, col or square
cell.setAllowed(~contains);
// As an extra step look for "naked singles",
// i.e. cells that have only one allowed value, and use
// that to set the answer (note this is different
// from the "value" as this can only be assigned
// by the user or any auto solve functions like "accept singles"
if (!cell.isAssigned()) {
this._isSolved = false;
if (count == 0)
this._isValid = false;
else if (count == 1)
}
}

// Step 2: Look for "hidden singles".
// For each row, col, square, count number of times each digit appears.
// If any appear once then set that as the answer for that cell.
// Count in rows
for (var i = 0; i < locs.length; i++) {
var loc = locs[i];
if (!this.checkForHiddenSingles(loc, SibType.Row))
// first check row sibs for a hiddne single
if (!this.checkForHiddenSingles(loc, SibType.Col))
// then check cols
this.checkForHiddenSingles(loc, SibType.Square);
// then check square
}

};```

The first step is to create an array representing each row, column, and square on the board. Using the `Location.grid()` method to provide a list of all locations on the board, we get each cell, obtain its value bit mask (sets bit N in the integer, all others 0), and OR them together to obtain a mask of all digits used in that row, column, or square, e.g., `rows[loc.row] |= contains`.

Next we step through each cell again and combine the digits used in that cell's row, column, and square using `var contains = rows[loc.row] | cols[loc.col] | squares[loc.getSquare()]`. If the cell has not been assigned, we set the allowed values as being the bitwise inverse. If only one value is in the allowed digits, we set the cell's "answer" as that digit - this is a naked single. I use the term answer but in fact it is just a good possibility.

In the final step of the `updateAllowed()` function, we use the allowed values for each cell to look for hidden singles, e.g., we scan a cell's row and if it has an allowed value that does not occur in any of its sibling cells, then it is a hidden single.

## Points of Interest

I learned a lot more about JavaScript in doing this article. It is suprisingly powerful but performance varies between browsers. For difficult problems (those with 18 or less givens), I found that Chrome was clearly the fastest.

## History

It would be interesting to try other Sudoku variants such as 25 x 25 ;-) when I have some spare time. Thanks for the comments to date. I have made several fixes to the current version based on these comments. In this second update to the article, I have added: an Undo button, a Hint button, and tooltips for all buttons.

## Share

 Product Manager Australia
No Biography provided

## You may also be interested in...

 First Prev Next
 Nice work Nasir Darwish24-Nov-13 0:49 Nasir Darwish 24-Nov-13 0:49
 My vote of 5 csharpbd23-May-13 2:00 csharpbd 23-May-13 2:00
 My vote of 5 Sudhakar Shinde6-May-13 2:26 Sudhakar Shinde 6-May-13 2:26
 My vote of 5 Savalia Manoj M13-Dec-12 17:41 Savalia Manoj M 13-Dec-12 17:41
 Why? Margo_Butterfly4-May-12 6:52 Margo_Butterfly 4-May-12 6:52
 Re: Why? Ron de Jong27-May-12 15:22 Ron de Jong 27-May-12 15:22
 My vote of 5... cassio.scherer15-Mar-12 9:48 cassio.scherer 15-Mar-12 9:48
 vote 5 shaheen_mix16-Dec-11 3:17 shaheen_mix 16-Dec-11 3:17
 My vote of 5 Anurag Gandhi13-Dec-11 20:56 Anurag Gandhi 13-Dec-11 20:56
 My vote of 5 Monjurul Habib12-Dec-11 10:50 Monjurul Habib 12-Dec-11 10:50
 My vote of 5 cseibar12-Dec-11 4:01 cseibar 12-Dec-11 4:01
 My vote of 5 maq_rohit12-Dec-11 3:47 maq_rohit 12-Dec-11 3:47
 New version uploaded Ron de Jong11-Dec-11 23:23 Ron de Jong 11-Dec-11 23:23
 Slight Problem SteveScanlon11-Dec-11 8:05 SteveScanlon 11-Dec-11 8:05
 Re: Slight Problem Ron de Jong11-Dec-11 23:19 Ron de Jong 11-Dec-11 23:19
 Re: Very good code Ron de Jong7-Dec-11 20:30 Ron de Jong 7-Dec-11 20:30
 Suggestions normanS6-Dec-11 22:21 normanS 6-Dec-11 22:21
 My vote of 5 Kanasz Robert1-Dec-11 3:43 Kanasz Robert 1-Dec-11 3:43
 My vote of 5 Sachin_Sharma(10)30-Nov-11 21:15 Sachin_Sharma(10) 30-Nov-11 21:15
 My vote of 5 Wooters30-Nov-11 15:04 Wooters 30-Nov-11 15:04
 Last Visit: 22-Feb-19 19:21     Last Update: 22-Feb-19 19:21 Refresh 1