The other day I thought about whether it would take a “while” for a computer to solve a sudoku puzzle using a naiive brute-force algorithm. I set out to find out.

In this article I use my bread-and-butter programming language Java to create such a solver in a kind of test driven way and also explore some simple optimizations.

Implementation idea:

  • use a backtracking algorithm, that means recursively go from cell to cell on the puzzle board and fill in numbers from 1 to 9 and check if all rules are satisfied. For example:
    1. It starts with top left, fill in “1”. All rules satisfied – got to the next.
    2. Fill in “1” – two 1s in a row – try with “2”, all rules satisfied, go to the next. And so on.
    3. If in a cell no number satisfy the rules, go back to the previous cell and try the next number there.
  • The puzzle board is represented as a 2-dimensional array.
  • The number “0” represents an empty cell.

Recap of the sudoku rules: In all horizontal and all vertical lines the numbers 1 to 9 are filled in exactly once plus in each 3×3 “subsquare” / “subboard” the numbers 1 to 9 are filled in exactly once.

Step 1: The Solver accepts an already completed board

When the board is already filled out, the Solver returns the board. It does not check if the board is correctly filled out. The following test checks this:

It creates a board (I call this “matrix” here) and fills it with “ones” except for the very first cell which gets a 5. It feeds it to the solver and checks whether it gets it back as solved.

Here is the code that accomplishes it:

The method “nextField” takes the current coordinates x and y and the matrix aka the board. It first checks whether it is just outside the board which means the board has been filled out. If so it returns the board. Otherwise if the current cell is already filled in, it recursivly calls the next cell. If the the current cell is not filled in, it returns an empty Optional, indicating it can’t fill in the cell.

Step 2: Adding the “horizontal rule”

Next we want to actually fill in numbers into an empty cell and check against the rule, that each row has pairwise distinct numbers in it.

First, here is the test:

It creates a board with each row numbers incrementally from one to nine and then “blanks” four cells. The solver should fill these cells with the correct numbers. Here is how it’s done (note: I introduce a “solve” method):

“isPotentialLegal” checks for distinct numbers by counting its occurences. It is called with all numbers of the current row. Zeros are “ignored”. If the rule is not satisfied, the next number is tried.

Step 3: Adding the “vertical rule”

Now I add the rule for columns. To create a test, I use a solved sudoku puzzle and clear some cells:

and later check for the correct solution.
The implementation is straight forward next to the “horizonal rule”:

Step 4: Adding the “subquadrant rule”

I wondered a bit about how to create a puzzle that would not be solvable without the subquadrant rule, but the original puzzle from Step 3 already did that. It has far more empty cells:

So here is the subquadrant rule. The key is to get the coordinates of the “subquadrant” right: integer division does the job, i.e. “(x/3)*3”. For example x=4 gets us “3” because it is the middle subquadrant starting at x=3. I use an extra method here because of the computation of the subquadrant start:

That did not made the test pass, though! It turned out I missed the backtracking-step, i.e. what happens when the recursion does not return a valid result – try next number (line 29):

Moreover, line 31 “empties” the cell so that we leave it in the starting state.

Conclusion

That’s it, I implemented a sudoku solver guided by tests. To answer my initial question: it’s fast. Well under one second! I will write a follow-up discussion some optimizations.