# 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.