# Simple Sudoku Solver

My first toy algorithm of 2014 was to build a Sudoku Solver (code below) using the brute force, recursive, depth-first search, deterministic, backtracking algorithm employed by many human players. This algorithm operates on N^2 x N^2 grids. So for a typical Sudoku board, N would equal 3.

The algorithm can simply be defined as follows:

- Given a row-major formatted puzzle, search for the 1st empty cell.
- If there are no empty cells, then simply return “true” as the puzzle is solved.
- For every possible value for that cell, check the 3 invariants:
- Check that value doesn’t already exist in the NxN grid
- Check that the value doesn’t already exist in the same row across the board
- Check that the value doesn’t already exist in the same column across the board

- If those invariants hold, then set the value for that empty cell to passing value, and recursively call this algorithm by going to Step 1.
- If the response is not “true”, then go to Step 3 while there are other possible untried values.

For typical Sudoku puzzles, the code below runs in sub-second time. For a slightly larger Sudoku (N=4) where numbers go from 1 to 16 takes *approximately 10 seconds* to process with this algorithm.

Advertisements

Leave a Comment