Sudoku

Entropy

Time taken (ms)

Itterations

Singles

Hiddens

Guesses

Backtracks

Run full solve for results

Sudoku Solving

Binary Style

Base game

Sudoku is played on a 9x9 grid filled with numbers ranging from 1 to 9 with a few rules dictating what numbers fit where.

No number in a single row may be the same as another of the same row
No number of a single column my be the same as another of the same column
No number within a 3x3 subgrid may be the same as another of the same 3x3 subgrid

Simple, right? Sudoku has no rules other than the previously stated ones.

First insights

JavaScript can represent a list on unique numbers as a Set. Think of them as a list of true false values, each representing whether or not a number exists in the Set.

JavaScript

const exampleSet = new Set([1,3,4,6,6]);

console.log(exampleSet);

=> Set(4) {1,3,4,6}

As can be seen above, adding a second 6 in the initializer will not keep said 6 in the final set. Using a set, we can represent all the numbers in a given row, column, and subgrid, without needing to check for repetition.

Since the start of this project, sets have gained in function and have become a lot better at handling this kind of problem. Before, to get the elements in common in two sets you had to do the following:

JavaScript

const setOne = new Set([1,3,4,6]);

const setTwo = new Set([4,8,7,1]);

let newSet = new Set();

[...setOne].forEach(number => {

if(!setTwo.has(number)) return;

newSet.add(number);

});

console.log(newSet);

=> Set(2) {1,4}

Loop through one set and check for the existence of the number in the other set, amazing. Amazingly inefficient that is.

Today, sets behave a bit more Array-like by having a "forEach" function implemented. There is also a direct "intersection" method to retrieve the common set of two sets.

JavaScript

const setOne = new Set([1,3,4,6]);

const setTwo = new Set([4,8,7,1]);

let newSet = setOne.intersection(setTwo);

console.log(newSet);

=> Set(2) {1,4}

Still however, there is a major concern when using Sets for this project. They are objects: When performing Set operations like above, we create a new Set object every time. This can be a major performance problem when we often need to perform multiple set operations for up to 81 cells

Sudoku has a total of 81 cells. We would need to loop through each row-, column-, and subgrid- set in order to see the options available to us. Of course, for sudoku, you don't really want the numbers in common, but rather those that are missing. A difference operation.

What we need is a non object data-type that can easily store multiple states at once and have operations performed on it to view its relation to others of its kind.

Enter, the bitset.

A bitset is a number whose binary representation is used to store 1s and 0s at desired places within the number. How these values are ready is up to the implementation.

Example: A single 32-bit number is enough to store monthly work-days. By assigning each day to a different bit position within the number, where 1 is a workday and 0 a vacation day, we can store 32 days, 1 more than the maximum a month can have.

The bitset implementation written for this project is called nSet (numeric Set) and can be found within implementation.

To show what benefits this has, lets review the earlier example of getting the common numbers of two sets:

JavaScript

const setOne = nSet.new([1,3,4,6]); // 101101

const setTwo = nSet.new([4,8,7,1]); // 11001001

let newSet = nSet.intersect(setOne,setTwo);

console.log(newSet);

=> 9 // 1001

At this point it should be clear how using basic numbers to represent the state of the board has some benefits over js Sets. They are not objects, are loved by our CPUs, and have minimal memory impact compared to Sets.

This is as far as this article goes. To learn more about the solving process, look at the nGrid, nSet or nArray implementation. (nArray is deprecated and not used in the project for reasons listed within its article)

Sudoku Solving

Binary Style

nGrid

The nGrid class contains all the implementation of the sudoku solver, like

Storing the current State
Keeping track of previous moves
Calculating possible numbers
...

In total, the solver knows five methods of figuring out numbers, although only three of them are active. The others have shown no performance gain. The active ones, in order of execution priority, are:

Obvious singles
Hidden singles
Guess and backtrack

Obvious singles

An obvious single is a cell that, by the rules, only has one remaining option. These are very easy to calculate as we are just looking for any cell where the combination of the row, column and subgrid nSet result in a single missing number.

Hidden singles

A hidden single can have many options, but one correct one. If along either row, column, or subgrid, it is the only cell to contain a certain option, that option is certain to be in that cell.

Since I am already using numbers to save the state of all groups, it wouldn't have felt right to keep track of encountered options in a dictionary, Array or Set, so I used two nSet numbers for each direction. The first being used to store potential hidden options, and the latter storing any hidden options that were found more than once.

Guess and backtrack

Similar to looking for obvious singles, the solver looks for the cell with the least options. If it spots a cell with two, it regards it as such and stops searching. If none is found, guess the lowest.

There is no heuristic to what number should be guessed, it simply always uses the first option.

To keep state, I transform every move into a number, using the first 21 bits to store row, column, the other options, and the guessed number. When backtracking, these numbers get extracted and undone.

Another way could have been to save the entire state of the board, one 81 element array for the cells and three 9 element arrays for the nSet numbers, and then overwrite the current state when backtracking. This was not done as it is likely that a guess is often invalid after less than twenty moves. If it is invalid after a mere five moves, this way would still need to store the entire 108 numbers. And due to there only being at most 64 unsolved cells, any guess is at most invalidated after 62 moves.

Sudoku Solving

Binary Style

nSet

nSet is a library written for this project. It is a JS Set like implementation using the bits of a number to store true and false flags as 1s and 0s.

JavaScript

let mySet = nSet.new([1,2,5,8]);

mySet = nSet.add(mySet,3);

mySet = nSet.add(mySet,8);

mySet = nSet.delete(mySet,1);

console.log(nSet.toArray(mySet))

=> [2,3,5,8]

Every function within nSet, besides creation and toArray, works in both constant time and space without branching.

Like JS Sets, nSet behaves similar to an Array, only a bit more since you can access elements by index. For example, it implements a shift() function that removes the first element in the set, in this case the lowest number.

new (Itterable args)

Generates a new nSet number, based on the input array.

JavaScript

let mySet = nSet.new([1,2,5,8]);

console.log(nSet.toArray(mySet))

=> [1,2,5,8]

Other functions like union, difference and intersect, along with utilities like has, isSingle and size, can be found in the source.

Sudoku Solving

Binary Style

nArray

This utility is like an nSet, only that each value uses 4 bits of a number. It was meant to replace the state of the board by storing the placed numbers in it.

However, JS only performs bit operations on 32 bit numbers, whereas 36 are needed to store nine 4-bit numbers. It is for this reason that the library was not used.