# Monthly Archives: December 2010

## Sudoku Solver

Earlier this week, I decided to try my hand at writing a solver for classic Sudoku puzzles. It was sort of a spur-of-the-moment sort of project, inspired by a friend that had to write something similar for an assignment. One of the Project Euler questions involves solving a set of 50 some Sudoku puzzles, so I figured I’d use the final code for my Euler solutions.

Initially, I wrote a very basic system designed to perform the classic process of elimination approach used by most human solvers. Of course, for the Euler question a good number of the puzzles were beyond such a solver and required a more powerful solution. My second iteration of the Sudoku solver used a basic brute-force approach by recursing through the vacant square and testing numbers. It was fairly efficient; it could solve easier puzzles in a few milliseconds, taking 20 or so for hard questions. I unfortunately have not gotten around to writing a logic-based “smart” solver yet, however this is definitely a topic I’d like to explore again in the future.

Just for anyone that’s curious, I plotted a few graphs that charted the active cell vs. the call number for the recursion function. The first graph shows a very basic puzzle, which only took around 280 recursive calls to reach a solution. The second shows a more tricky puzzle, which took a little less than 4,500 calls. The worst case puzzle, pulled from a Wikipedia article, took some 300,000 calls and had such a large dataset that Excel decided it didn’t want to function properly (read: it crashed).

Easy Sudoku graph:

Hard Sudoku graph:

That’s all for now!

T