Sudoku Solver (Part 1c) - Improve solver speed

Satisfaction Frontier

In my last article, I decided to review the world’s fastest sudoku solver and the corresponding code and see if I could learn a thing or two.

It was very informative. You should read the summary as it contains amazing information that I can not possibly do a great job of summarizing myself.

Some of the key insights that I took from that article was:

1. Send as many bits to the processor as you can.
2. Arrange your bits for optimal performance, not optimal space savings.
3. Don’t look for solutions in places where the game is already solved.

Ok, so those are pretty vague, but they were tremendously helpful for me. Using inspiration from their code, I made a few changes.

1. I created a 64-bit ULong to represent each Row, Column, or Box. I only use 40 bits. Every 4 bits is the count of cells that could have that digit (max = 9, min = 0 if digit is solved). Bits 36-40 represent how many cells are solved.
2. I created logic to support this value that allowed me to quickly determine if a row, column, or box was solved already and avoid processing it again.
3. I can determine quickly if a row, column, or box has a single value in a cell by referencing an array of 9 hard-coded values indicating only a single cell can have that digit.

Doing those 3 things increased the performance significantly in both easy and hard Sudoku puzzle sets. I summarize this below:

What do I do next?

I am grateful that there are amazing developers that share their code online and I learned a ton reading an extremely fast sudoku solver.

I think I could make some gains by switching to C++ from C#, changing the code entirely to use the Triad structure described in tdoku, or I can accept things as they are.

For now, I am done trying to make the code faster. I need to accept that this code is acceptably performant and move on to the rest of this project.

Thanks for reading part 1c of my quest to build a CV sudoku solver. You can find the code on my github.