Sudoku Solver

December 7, 2022 - Reading time: 4 minutes

The Sudoku Solver on the site lets you contribute boards to a shared public library, and lets you choose from a list to see the original board, and its solution.

A Sudoku solver is the perfect project for learning a new scripting language, or trying a new algorithm.  As a puzzle, it can be anywhere from easy to extremely hard to solve, but it yields pretty easily to algorithmic solvers.

I’ve written solvers in Perl, Python, and most recently PHP, using a variety of techniques.  All of which come with a single lesson: don’t over-think the problem.

My first attempt was a rule-based system that tried to encapsulate the heuristics I had developed (so far) while solving the puzzle with pen-and-paper.  It worked, but was kind of clunky, and it was easy to get to a place where I still had cells to fill, but had run out of useful rules. 

To stay faithful to the approach, I needed more (and better) rules to get past the dead-ends.  When I later discovered the YouTube channel “Cracking the Cryptic”, my eyes were opened to whole new ways to expand what had been, in fact, a very paltry rule set. 

Solving Sudoku by hand is like a yoga or meditation practice.  A long-term, persistent practice of trying to improve your mental game for spotting patterns on the board.

One scripting opportunity would have been to try expanding the rule library I started with, and to deploy more exotic rules, but I decided to try instead a few other avenues:

I built an extension on the rule-based system that just added a recursive final step … when the rules tapped out, I identified an open cell with a small number of numbers that might work, and looped through them: plug in a guess and then see if the rule-based system could advance from there.  If it failed, back up, and try the next guess.  Slightly inelegant but it worked and was fast.

When I was learning Python, I started over and wrote a simple Depth First solver, which had been an approach I’d used on some quirky jigsaw puzzles to great success.  The idea here is that instead of using rules, you just proceed to the first blank on the board and loop a number into it, check for any failure states (like the number repeats in the given row or column, etc).  If you find a failure, back up and try the next number in the loop; otherwise move on to the next blank cell and start a loop on that one.  This approach works but turns out to be massively slow.  Although Depth First is a great way to prune away branches of a combinatorial tree, this was still a really big tree.  I ported the script to Perl to see if it was an interpreter issue (also to create a terminal display for no redeeming reason) but …. just really slow.

For the puzzle solver on the current site, I used a trick I’d seen my father use in manual solves:  imagine a keypad, 1 to 9, for each blank cell, and only include numbers in the keypad that you can’t find in the row, column, or local 3x3 matrix for the blank cell.  Inventory the whole board this way. When you find a cell where only one number works (and you usually will), fill that number in, and then refresh your inventory of blank-cell keypads to reflect this addition.  When out of single-number solutions for cells, identify a cell with the smallest number of digits remaining on its keypad, and loop through those remaining digits (fill in and recurse to one level down, popping back up a level when you hit a failure situation).

This final approach turns out to be very fast.  I wrote it first in Python.  The PHP version for the site solves even difficult puzzles and creates graphical versions of the initial board and a the solution to display, all without much of a pause loading the page.

The lesson: if you are a person with only your brain and a pen between you and the sudoku board, you are practicing a meditation and should approach it as such.  If you are using a computer, don’t over-complicate it, and let simple loops and recursion do the heavy lifting.

This several solver scripts (including a couple attempting a depth-first approach) can be found in this GitHub repository.