Solving Sudoku using Hyperdimensional Computing

Alright, everyone. We're all familiar with Sudoku and the standard ways to solve it computationally. Typically, you'd use a backtracking algorithm that enforces constraints: you try placing a number, check if it violates the row, column, or box rules, and proceed or backtrack. That rule-checking part is usually done by maintaining sets or boolean arrays for each group.

Today, I want to explore a different approach for that core task of constraint checking, using a technique from computational neuroscience and AI called Vector Symbolic Architectures, or VSA.

The fundamental idea is to represent symbolic information—in our case, the digits 1 through 9—not as simple integers, but as unique, high-dimensional vectors. Think of them as dense numerical fingerprints.

The power of this representation comes from how we can combine them. The state of an entire row, column, or box can be represented by a single "summary" vector, created by simply adding the vectors of all the digits it contains. This is called bundling. All the information is superimposed into one vector.

The most crucial part is querying. We can take a group's summary vector and efficiently check for the presence of a specific digit's vector. The operation we use for this is circular correlation, which we can compute very quickly using Fast Fourier Transforms (FFTs). If the correlation is high, the digit is already in that group. If it's near zero, the spot is open.

So, in this solver, we maintain 27 of these summary vectors—one for each row, column, and box. To determine all legal moves on the board, we perform these VSA-based checks in a highly parallel way. This core legality engine is then plugged into a familiar backtracking search framework with heuristics like Minimum Remaining Values (MRV).

This is less about creating the world's fastest solver and more about demonstrating a powerful and alternative way to represent and manipulate structured, symbolic data. Let's dive into the implementation.

Methodology

Our proposed Sudoku solver integrates a Vector Symbolic Architecture (VSA) for constraint representation and checking within a deterministic backtracking search algorithm. The methodology can be conceptually divided into two primary components: 1) a VSA-based constraint module that efficiently computes the set of all legal moves across the entire board in parallel, and 2) a heuristic search module that utilizes this information to navigate the search space via constraint propagation and guided exploration.

High Level Intuition

At its core, the VSA module replaces the traditional, discrete method of checking for rule violations. Instead of iterating through a cell's row, column, and box to see if a number is already present, we represent each of these 27 constraint groups as a single high-dimensional vector. Each vector acts as a superimposed "summary" of all the digits it contains.

The key insight is that we can query these summary vectors with extreme efficiency. In a single, batched operation, we can "ask" all 27 groups which digits they contain. This yields a complete map of number placements, from which we can deduce a boolean mask of all legal moves for every empty cell on the board. This legality mask then drives a standard but powerful search algorithm, allowing it to propagate forced moves (singletons) and make intelligent guesses when necessary.

VSA Representation of Board State

The foundation of our method is the mapping of discrete Sudoku symbols (digits) and group states into a continuous vector space.

Item Vectors for Digits

Each digit is mapped to a unique -dimensional item vector . These vectors are designed to be quasi-orthogonal. We construct them deterministically using circular shifts of a single random base vector , where is drawn from a standard normal distribution and normalized.

This construction, known as a shift-code, is computationally inexpensive and provides the necessary algebraic properties for our similarity checks. The dimensionality is chosen to be large enough to minimize incidental correlations between vectors.

Bundling for Constraint Groups

The state of each of the 27 constraint groups (9 rows, 9 columns, 9 boxes) is represented by a single summary vector. For any group , its summary vector ​ is formed by the element-wise summation of the item vectors corresponding to the digits currently placed within that group. This operation is known as bundling.

where ​ is the set of digits in group . This bundling operation effectively superimposes the vector representations of all constituent digits into a single composite vector. The solver maintains 27 such vectors representing the complete state of the board's constraints. These vectors are updated incrementally: when a digit is placed, its item vector is added to the corresponding three summary vectors; when a move is undone, it is subtracted.

Computing the Legal Move Mask

The central task of the VSA module is to produce a boolean tensor, where ​ is true if and only if placing digit at cell i is a legal move. This is accomplished in a highly parallelized manner.

Duplicate Detection via Circular Correlation

To determine which digits are present in each group, we use circular correlation as a similarity metric. Due to the properties of our shift-code item vectors, the correlation of a summary vector ​ with the base vector reveals the presence of all digits simultaneously. This operation is computationally expensive in the time domain but can be calculated efficiently in the Fourier domain:

wheredenotes the Fast Fourier Transform (FFT), ​ is the complex conjugate of the transform of , and is the element-wise product. The -th element of the resulting vector gives a high response if the vector was part of the bundle ​, and a near-zero response otherwise.

Critically, we compute this for all 27 groups in a single batch. The summary vectors for all rows, columns, and boxes are stacked into a tensor of shape . The batched FFT-based correlation yields three count matrices of shape , and . Each element approximates the integer count of digit d in group , which for a valid state will be either or .

I have introduced the idea of detecting duplicates in sets using Vector Symbolic Architectures in another article - Encoding Multiplicity: Fast Duplicate Detection using Hyper-Dimensional Computing which explains the concept at length.

Constructing the Boolean Mask

With these three count matrices, the final legality mask L is constructed. A move is legal if the cell is empty and the count for digit is zero in all of cell 's corresponding groups (row ​, column ​, and box ​). This logic is vectorized across all 81 cells:

This entire pipeline—from 27 summary vectors to the final mask—constitutes a single forward pass of the VSA constraint module.

Heuristic Search Algorithm

The solver embeds the VSA module within a deterministic backtracking search framework. This algorithm's effectiveness comes from its ability to aggressively prune the search space by combining advanced constraint propagation with intelligent heuristic choices.

1. Constraint Propagation

Before making any guesses, the solver first resolves all logically forced moves. It does this by repeatedly applying propagation rules until no more deductions can be made (a "fixed point"). This process now includes two key techniques that operate on the VSA-generated legality mask.

1. Naked and Hidden Singles

The algorithm first identifies the most obvious forced moves:

  • Naked Singles: Any empty cell that has only one legal candidate. This is the simplest constraint to find.

  • Hidden Singles: A more powerful technique that looks at constraints from a digit's perspective. A hidden single occurs when a missing digit can only be placed in one possible cell within an entire unit (row, column, or box), even if that cell has other candidates.

For example, consider Row 2 below. The digit '7' is missing.

+-------+-------+-------+
| 5 3 4 | 6 7 8 | 9 1 2 |
| 6 7 2 | 1 9 5 | 3 4 8 |
| 1 9 8 | 3 4 2 | . . . |  <-- Looking for a '7' in this row.
+-------+-------+-------+
...

Let's say the legal mask shows the three empty cells have the following candidates:

  • Cell (2, 6): Candidates {5}

  • Cell (2, 7): Candidates {5, 7}

  • Cell (2, 8): Candidates {5}

Although Cell (2, 7) has two candidates ({5, 7}), it is the only cell in the entire row that can accept a '7'. Therefore, it is a hidden single, and the solver will confidently place the '7' there.

2. Early Pruning via Contradiction Detection

This propagation step also serves as a powerful method for detecting dead ends early. While scanning a unit for hidden singles, the algorithm might find that a missing digit has zero possible cells. For instance, if Row 2 was missing a '7' but no empty cell in that row could legally accept a '7', the current board state is invalid.

This contradiction immediately tells the solver that its last guess was wrong. It prunes this entire search branch and backtracks without wasting any more time.

3. Heuristic Choice Point (MRV + Corrected LCV)

When propagation is complete and the puzzle is still unsolved, the solver must make a guess.

1. Minimum Remaining Values (MRV)

To decide which cell to guess on, the solver picks the one with the Minimum Remaining Values. It chooses the empty cell with the fewest legal candidates, as this is the most constrained part of the puzzle and will likely lead to a contradiction faster if the guess is wrong.

2. Least Constraining Value (LCV)

To decide which number to place in that chosen cell, the solver uses the Least Constraining Value heuristic. The logic here is to pick the digit that causes the least disruption to its neighbors. The corrected implementation does this by choosing the digit that is also a legal candidate for the most peer cells. This leaves the maximum number of future options open for its neighbors, making it a more robust and effective guess.

3. Backtracking

The solver uses a stack to manage decision points. When it makes a heuristic choice, it pushes the alternative options onto the stack. If a subsequent state leads to a contradiction (i.e., an empty cell has zero legal candidates), the solver backtracks by popping the last decision point from the stack, reverting the board state (by subtracting the relevant item vectors), and trying the next available option. The process terminates upon finding a complete solution or exhausting the search space.

Experiment and Implementation

I implemented a prototype of an end-to-end implementation and an experimental setup to generate random sudoku puzzles of different difficulty levels and evaluated the method on them. The code is written in Python and is available in this github repo .

Below is the output of running the script. The output shows the success rates - the percentage of puzzles solved out of 500 puzzles for each level of difficulty along with the average steps taken to solve as well as time taken to solve.

=== Easy (clues=45) — n=500 ===
Success rate: 100.0%
Avg time:     1.9 ms
Avg steps:    36.0

Sample Puzzle:
+-------+-------+-------+
| 3 . . | 8 5 . | . 9 . |
| . 8 . | 6 . . | 4 1 3 |
| 2 . 9 | 4 3 1 | 8 . 5 |
+-------+-------+-------+
| . 1 2 | 7 8 3 | . 5 . |
| . 7 3 | . . . | . 2 4 |
| 6 . . | . . . | 7 . 8 |
+-------+-------+-------+
| 7 3 . | . . 8 | 2 6 1 |
| 1 2 6 | 3 . . | . . . |
| . . 8 | 2 1 6 | 3 4 . |
+-------+-------+-------+
Sample Solution (verified):
+-------+-------+-------+
| 3 4 1 | 8 5 7 | 6 9 2 |
| 5 8 7 | 6 2 9 | 4 1 3 |
| 2 6 9 | 4 3 1 | 8 7 5 |
+-------+-------+-------+
| 4 1 2 | 7 8 3 | 9 5 6 |
| 8 7 3 | 9 6 5 | 1 2 4 |
| 6 9 5 | 1 4 2 | 7 3 8 |
+-------+-------+-------+
| 7 3 4 | 5 9 8 | 2 6 1 |
| 1 2 6 | 3 7 4 | 5 8 9 |
| 9 5 8 | 2 1 6 | 3 4 7 |
+-------+-------+-------+

=== Medium (clues=33) — n=500 ===
Success rate: 98.6%
Avg time:     6.0 ms
Avg steps:    51.5

Sample Puzzle:
+-------+-------+-------+
| . 2 . | . . 4 | . 7 . |
| . 7 . | 5 . . | . 4 3 |
| 3 . . | 9 . 7 | . 2 8 |
+-------+-------+-------+
| . 3 4 | . 5 . | . . . |
| 5 . 7 | . . . | 4 . 9 |
| 6 8 . | . . 3 | . . . |
+-------+-------+-------+
| . . . | . 4 6 | 3 9 . |
| 4 . . | . 7 . | . 5 . |
| . . 3 | 1 . 5 | . . 4 |
+-------+-------+-------+
Sample Solution (verified):
+-------+-------+-------+
| 1 2 6 | 8 3 4 | 9 7 5 |
| 8 7 9 | 5 1 2 | 6 4 3 |
| 3 4 5 | 9 6 7 | 1 2 8 |
+-------+-------+-------+
| 9 3 4 | 7 5 1 | 2 8 6 |
| 5 1 7 | 6 2 8 | 4 3 9 |
| 6 8 2 | 4 9 3 | 5 1 7 |
+-------+-------+-------+
| 7 5 8 | 2 4 6 | 3 9 1 |
| 4 6 1 | 3 7 9 | 8 5 2 |
| 2 9 3 | 1 8 5 | 7 6 4 |
+-------+-------+-------+

=== Hard (clues=26) — n=500 ===
Success rate: 97.8%
Avg time:     12.1 ms
Avg steps:    69.9

Sample Puzzle:
+-------+-------+-------+
| 8 2 9 | . . 5 | . . . |
| 6 . . | . . . | . 2 9 |
| . 3 . | 8 . . | . . . |
+-------+-------+-------+
| 5 . . | . 6 . | 2 . 1 |
| . 4 . | . 8 . | . . 6 |
| 3 7 . | 2 . . | . . . |
+-------+-------+-------+
| 4 6 . | . 2 . | . . . |
| . . . | . 3 . | . . 2 |
| . . . | 7 . . | . 6 . |
+-------+-------+-------+
Sample Solution (verified):
+-------+-------+-------+
| 8 2 9 | 6 1 5 | 4 3 7 |
| 6 1 5 | 3 7 4 | 8 2 9 |
| 7 3 4 | 8 9 2 | 6 1 5 |
+-------+-------+-------+
| 5 9 8 | 4 6 3 | 2 7 1 |
| 1 4 2 | 9 8 7 | 3 5 6 |
| 3 7 6 | 2 5 1 | 9 8 4 |
+-------+-------+-------+
| 4 6 1 | 5 2 8 | 7 9 3 |
| 9 8 7 | 1 3 6 | 5 4 2 |
| 2 5 3 | 7 4 9 | 1 6 8 |
+-------+-------+-------+

Conclusion

We began this journey not to create the world's fastest Sudoku solver, but to explore a fundamentally different way of thinking about the problem. By stepping away from traditional discrete sets and arrays, we demonstrated that the complex, symbolic rules of Sudoku can be elegantly captured in the continuous, high-dimensional space of Vector Symbolic Architectures.

The core of our method—representing each row, column, and box as a single superimposed vector—proved to be a powerful concept. Using batched FFTs for circular correlation, we could generate a complete legality mask for the entire board with remarkable efficiency. This VSA-powered engine, when coupled with classic AI search heuristics like MRV, LCV, and enhanced propagation techniques, resulted in a solver that is both robust and capable, successfully tackling even difficult puzzles.

Ultimately, this project serves as a compelling bridge between two worlds: the crisp logic of symbolic reasoning and the distributed, pattern-matching nature of vector-based computation. It's a tangible example of how abstract constraints can be encoded, manipulated, and queried in a framework that feels right at home in the modern machine learning landscape. Hopefully, it inspires you to look at old problems in new ways and to not be afraid of trading the conventional for the curious.