## 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 () {
var cols = new Array(BoardSize);
var rows = new Array(BoardSize);
var squares = new Array(BoardSize);
var locs = Location.grid();
for (var i = 0; i < locs.length; i++) {
var loc = locs[i];
var contains = this.getCell(loc).valueMask();
rows[loc.row] |= contains;
cols[loc.col] |= contains;
squares[loc.getSquare()] |= contains;
}
this._isValid = true;
this._isSolved = true;
for (var i = 0; i < locs.length; i++) {
var loc = locs[i];
var contains = rows[loc.row] | cols[loc.col] | squares[loc.getSquare()];
var cell = this.getCell(loc);
cell.setAllowed(~contains);
cell.setAnswer(0);
if (!cell.isAssigned()) {
this._isSolved = false;
var mask = new AllowedValues(~contains);
var count = mask.count();
if (count == 0)
this._isValid = false;
else if (count == 1)
cell.setAnswer(mask.getSingle());
}
}
for (var i = 0; i < locs.length; i++) {
var loc = locs[i];
if (!this.checkForHiddenSingles(loc, SibType.Row))
if (!this.checkForHiddenSingles(loc, SibType.Col))
this.checkForHiddenSingles(loc, SibType.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.