HTML5 Sudoku Solver

• Download source code - 8.1 KB

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
        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);
        // set allowed values to what values are not
        // already set in this row, col or square
        cell.setAllowed(~contains);
        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 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.