The recursion in the guessing logic of my old Sudoku solver was flawed — often finishing without a complete puzzle. So I’ve rewritten it and I’ll be putting it in another post after this one.

In this post, I want to talk about speed. As I was fixing my code, I realized that I could probably just isolate my guessing process and just solve the Sudoku puzzle by first guessing based on the possibilities of a given cell, reducing the possibilities in that row/column/square, and then guessing again. This process would be repeated until the entire puzzle was solved, or until we reached a condition where our guess was wrong and we had to go back and try a different guess.

What I found is that for the hardest puzzles, where multiple solutions are likely, using only the guessing process could yield a result in ~3 seconds. However, if I used my original code based on comparisons that reduce the possibilities for a given cell, the puzzle would be solved in ~13 seconds.

However, in an easier puzzle, where many cells are already given and only one solution exists, my original code was faster than my guess-only code: 1.2 seconds vs 2-4 seconds respectively. My original code would consistently produce a solution within 1.2 seconds whereas the guess-only code has a random element to its guessing logic, leading to a variable solution time.

The speed difference is due to the set comparisons going on in my original code. It searches every single cell for patterns in its row/column/square in order to reduce the number of possibilities. In an easy puzzle where there aren’t very many possibilities to begin with (2-4 possibilities per cell), this comparison is fairly efficient. However, when the number of possibilities expands for the harder puzzles, these comparisons are no longer efficient and you inevitably end up guessing to solve the puzzle.

On one hand, I’m a little bummed that logic is slower than guessing against harder puzzles. But on the other, I can deal with it. When doing a Sudoku puzzle by hand, it’s not hard to get in a rut and feel the temptation to guess. Computers just have an easier time with keeping track of failed guesses. And in a harder puzzle where guessing is inevitable, it ends up being faster if you just started guessing from the start.

Advertisements