JavaScript Sudoku solver

My wife has developed a passion for Sudoku. I do not share it, I've always thought that this is a problem for computers, not humans, so I've never tried to solve one by hand. However, even if it's a high school problem, I thought it'd be a cute little program to work on. This is the obligatory blog post about it.

Update: see bestest version.

Problem definition

It's pretty simple. You are given a board like this:

You have to fill every empty cell with a non-zero digit [1..9], such that no digit appears twice on the same column, row, or within the same 3x3 square. Click any empty field to see a list of allowed digits.

It's a search problem, so the tool that comes to mind is backtracking. Some developers have an anxiety about this word, as if it's some kind of weird black magic, but really, it's pretty simple. I'll describe here my sudoku solver.

Board representation

Since it has 81 cells, we'll keep it as an array with 81 digits (zero for empty cells). It will be convenient to access it both using an index 0..80, or as (row, column), so we'll have a couple of functions to convert between the two:

// index -> { row, col }
function i2rc(index) {
    return { row: Math.floor(index / 9), col: index % 9 };
}

// { row, col } -> index
function rc2i(row, col) {
    return row * 9 + col;
}

Next, we need a function that tells us what are the available choices, that is, what digits are acceptable in a given cell (I'm also gonna call them “moves”). Here's a reasonable implementation:

function getChoices(board, index) {
    let choices = [];
    for (let value = 1; value <= 9; ++value) {
        if (acceptable(board, index, value)) {
            choices.push(value);
        }
    }
    return choices;
}

The board is our array with 81 elements, and index is 0..80 — this function will return an array of digits that are currently permitted on the cell at this index, according to the rules of the puzzle.

The actual rules of the puzzle are implemented in the function acceptable: we can use a digit if it's not already used on the same row, column or in the same 3x3 square. So here it is:

function acceptable(board, index, value) {
    let { row, col } = i2rc(index);

    // if already present on the column, not acceptable
    for (let r = 0; r < 9; ++r)
        if (board[rc2i(r, col)] == value) return false;

    // if already present on the row, not acceptable
    for (let c = 0; c < 9; ++c)
        if (board[rc2i(row, c)] == value) return false;

    // if already present in the same 3x3 square, also not acceptable
    let r1 = Math.floor(row / 3) * 3;
    let c1 = Math.floor(col / 3) * 3;
    for (let r = r1; r < r1 + 3; ++r) {
        for (let c = c1; c < c1 + 3; ++c) {
            if (board[rc2i(r, c)] == value) return false;
        }
    }

    // we have a "go"
    return true;
}

There are optimizations we could make (we could use a single loop, and we could skip converting between index/row,column with some clever tricks) but let's not bother. We better start working on the problem now, that is, let's write a function that figures out the solution for a given puzzle.

The “brute force” approach

As the name sounds, this is pretty dumb. We'll iterate through the empty cells, assign to each one of the acceptable digits and try to move as far as we can. If we can manage to fill the whole board, then the problem is solved, and if we get to a point where there are no acceptable digits, we have to “backtrack” — reach back to the previous cell where we had multiple choices, and pick something else. It's trivial to write this function. For convenience, let's assume board is an external variable; our solver function only has to receive the current index — the cell that it currently deals with. It will return true if it found a solution, and false otherwise.

function solve(index) {
    while (index < 81 && board[index]) ++index; // skip non-empty cells
    if (index == 81) return true;               // we filled'em all, success!
    let moves = getChoices(board, index);
    for (let m of moves) {
        board[index] = m;              // try one choice
        if (solve(index + 1))          // if we can solve for the next cell
            return true;               // then return true, success!
    }
    board[index] = 0;  // no move worked; we failed, clear the cell
    return false;      // and backtrack
}

You can play with it below, select a few samples (or clear the board and enter your own). “Solve!” will solve it instantly, while “Play” will step through it so you can see how it fills the cells, and how it backtracks when it needs to try different values. When it's done it will tell you how many moves it had to take back. Note that “Play” will take a long time on this unoptimized version, so don't bother to wait for it to complete; you can use “Pause” or “Reset” to stop it.

If you try the the “really hard” puzzle, the brute-force search has to backtrack 8.9 million times and takes a few seconds.

An improvement: move ordering

How does a human approach the problem? Intuitively, we look at the whole board and pick the cells where we have little choices. Ideally, if we can determine that only one value is possible, then we write it down and forget about it.

This leads us to the “greedy” search: instead of trying values for each cell in order, fill first those cells where we have the fewest acceptable choices — that is, there's a smaller probability that we'll change our mind about it. Here's the new solve function:

function solve() {
    let { index, moves } = bestBet(board);    // find the best place to fill
    if (index == null) return true;           // we filled'em all, success!
    for (let m of moves) {
        board[index] = m;                     // try one choice
        if (solve()) return true;             // if we solved further, success!
    }
    board[index] = 0;                         // no digit fits here, backtrack!
    return false;
}

So this time our function doesn't need to take the index as an argument, instead it'll determine the next index to fill using bestBet — a new function that will return the index of the cell with the fewest possible moves. Since, in order to figure that out, it needs to compute the moves too, it will return them as well, so that we avoid another call to getChoices. Here is bestBet:

function bestBet(board) {
    let index, moves, bestLen = 100;
    for (let i = 0; i < 81; ++i) {
        if (!board[i]) {
            let m = getChoices(board, i);
            if (m.length < bestLen) {
                bestLen = m.length;
                moves = m;
                index = i;
                if (bestLen == 0) break;
            }
        }
    }
    return { index, moves };
}

Below you can play with the new algorithm (or rather, it's the same algorithm, it just tries moves in a different order) and you can see that it makes a world of difference (look at the number of take-backs, compared to the previous implementation). On this new version, “Play” will complete within a few seconds for any of the medium examples.

We can notice a significant reduction of the search tree (much fewer take-backs, for example the “really hard” puzzle backtracks 430K instead of 8.9M times). However for most puzzles the actual run time is a bit higher! This got me thinking. Every time we call search(), bestBet will repeat most work it already did on the previous iteration, looking for the best place to fill and computing moves for every single field, again. To make this optimization worthy of its cost we need to add some ugliness (with some clever tricks in bestBet we could cache part of the results), but I won't do it here.

More human touch

Maybe I'd stop here, but my wife, who actually solves sudoku with her brain, told me a little trick that I didn't consider (I probably would have thought about it, had I ever tried to solve sudoku by hand). Look at the board below and focus on the yellow cell. Click on it to see what my program thinks are the available moves.

You see, it claims that the allowed digits for that field are 2, 4, 5, 8, 9, and that's correct by the rules, but now if you look at the pink fields, you can see that 8 is not allowed on the 4th and 6th columns, nor on the 3rd row, because an 8 is already there. And still we know that the top-middle 3x3 square must contain an 8, and this leaves the yellow cell as the only option; clearly we have an unique choice there, we can fill it immediately and there's no need to try 2, 4, 5 or 9.

Implementing this new optimization is not hard and makes a new world of difference, because it applies not only to the initial configuration but also after every subsequent move that the algorithm tries. Check the new numbers:

The “really hard” puzzle now takes less than half a second and only backtracks 26K times, a huge reduction of the search tree.

To implement this new optimization we only have to improve getChoices, using a new utility function which implementes the trick:

function getChoices(board, index) {
    let choices = [];
    for (let value = 1; value <= 9; ++value) {
        if (acceptable(board, index, value)) {
            if (unique(board, index, value))
                return [ value ]; // it's useless to try anything else
            else
                choices.push(value);
        }
    }
    return choices;
}

function unique(board, index, value) {
    let { row, col } = i2rc(index);
    let r1 = Math.floor(row / 3) * 3;
    let c1 = Math.floor(col / 3) * 3;
    for (let r = r1; r < r1 + 3; ++r) {
        for (let c = c1; c < c1 + 3; ++c) {
            let i = rc2i(r, c);
            if (i != index && !board[i] && acceptable(board, i, value)) {
                return false;
            }
        }
    }
    return true;
}

The code

Here is the script used for the boards in this page. The code isn't exactly pretty, I made it just for the purpose of this blog post. Use it like this:

import { Sudoku } from "sudoku.js";
let sdk = new Sudoku(document.querySelector("#container"), {
    smartOrdering: true,
    smartChoices: true
});
sdk.writeBoard([
    0, 0, 0,  0, 0, 0,  0, 0, 6,
    0, 3, 0,  0, 7, 1,  0, 4, 0,
    0, 0, 0,  0, 0, 0,  8, 0, 0,

    0, 0, 0,  9, 0, 8,  0, 7, 1,
    1, 0, 3,  0, 0, 0,  0, 0, 0,
    0, 0, 2,  0, 3, 0,  9, 0, 0,

    5, 0, 7,  0, 0, 6,  0, 0, 0,
    2, 0, 0,  0, 0, 0,  7, 0, 0,
    0, 0, 1,  8, 0, 0,  0, 0, 2,
], true);

Fastest version yet (see below)

Update: leaving this here, but I've got a better version in the next section.

“The rest is engineering”. I couldn't figure out any more algorithmic improvements, but I couldn't help it and I've micro-optimized the heck out of it. Here's the “really hard” puzzle on the best version I've got:

If you're wondering what changed, look at the acceptable function (I used a single loop to iterate across both row and column; using the same loop to iterate through the 3x3 square seems to do more harm than good). Also at bestBet — I inlined getChoices into it and instead of building an array of moves, we bit-code them into an integer in order to avoid allocations, because the garbage collector costs time. And solve was updated accordingly.

Bestest version :)

With even more engineering, but also an important improvement in the unique function, the “Really Hard™” puzzle turns out to be Actually Quite Simple™ and the algorithm solves it in just a few milliseconds with only 7 take-backs. Here is the bestest version.

Note: the hardest puzzle in this example is actually the one named “Harder”. It doesn't seem to be designed for humans, as no digit can be placed safely in the initial configuration (or I can't see it). The computer has to guess 1209 times (meaning, there are as many situations in which it can't place a safe digit and has to chose among multiple options).

The new unique function checks for uniqueness not only within the 3x3 block, but also on the whole row and column, which again drastically reduces the search tree. As for the engineering improvements: instead of storing digits as decimals, they are now bit-coded (each digit's corresponding bit is set). This allows us to use bitwise operations to detect available choices (getChoices was renamed getMoves), which turns out to be much faster. There are other improvements as well, but this post is a bit too long already, feel free to check the code.

Add your comment