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 – particulary when I hit a hard problem!

A screen shot 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 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 s standard Sudoku term and refers to a case where an llowed 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. The Load button was already mentioned 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. Its 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. The other buttons we haven’t covered are the Clear button which basically clears every cell including givens; Accept will convert a “single” into an actual value and Solve solves the entire problem. 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 succesful 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: the row and column. It is used to simplify calculations and provides useful functions like a list of locatons 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 calculting 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
			var contains = this.getCell(loc).valueMask();
			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);
			cell.setAllowed(~contains); // set allowed values to what values are not already set in this row, col or square
			cell.setAnswer(0); //clear any previous answers
			// 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;
				var mask = new AllowedValues(~contains);
				var count = mask.count();
				if (count == 0)
					this._isValid = false;
				else if (count == 1)
					cell.setAnswer(mask.getSingle());
			}
		}

		// 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
		}

		// TO DO: Add code here to detect naked/hidden doubles/triples/quads
	};

//

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 cells “answer” as that digit – this is a naked single. I use the term answer but in fact it just a good possible.

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 its a hiddne 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 those comments.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)