How I wrote a Sudoku Solver Program!

A few months ago, I wrote a Sudoku Solver program. It solves 9x9 Sudoku puzzles, instantly on any modern PC.

It was a long ordeal, I first started it just before my winter semesters, and the brute-force solver I came up with, would perhaps take hours to come to a solution in moderately hard sudoku puzzles. It was only after I took a Discrete Optimization course on Coursera (which I never completed :D), and more importantly, solved the Diabolic Sudoku puzzles myself  (for the first time :p ), with pencil-n-paper, that I came up with the idea of the fast solver, that actually worked.

Before I start with the programming part, I would like to write up a bit of background knowledge.

There are a lot of tricks to solve Sudoku with pencil-n-paper. We usually use deductive reasoning, i.e. we see the filled up boxes, mark the boxes with numbers that might fill up, and eliminate the impossible. If now there's a box with only one possibility, fill it up, and continue.

But often this basic strategy doesn't work too well with anything more than the cakewalk puzzles. Then we have to use other, bit more advanced tricks. Although I would love to enumerate those myself, but I don't think its mine to write, I learned those from these few websites:

1. http://www.paulspages.co.uk/sudoku/howtosolve/

2. http://www.sudokudragon.com/sudokustrategy.htm

3. http://www.sudokuoftheday.com/pages/techniques-overview.php

Caution: Much of the material above is redundant :) That is a long list of techniques.

The Catch? You might need them to solve hardest Sudoku on paper, but your PC can use backtracking. We can sacrifice a few milliseconds of speed for a simpler program. So we can program only a few of them, and even the hardest puzzles will be solved in small fractions of a second.

So, this is what I did:

1. Fill in all the empty boxes, with options, i.e. numbers that may fill the boxes, given the already filled up boxes, and no constraints (rules of game) are violated.

2. Check for locked pairs. See what locked pairs mean? or here. Now remove options, as appropriate.

3. Now see if there's any box with only one option left. If yes, then fill it.

4. If no box was filled in last step, the program needs to make a guess.  Find the box with least possible options. This is in accordance to the fail-first principle. Lesser the options, lesser to backtrack!

5. If the program gets stuck, i.e. at some point, there is nothing program can do, and the puzzle isn't yet solved, go to the last state, that's the point from which the decision was made, and take another decision.

In any of these states, prune the search space, by steps 1-3.

6. At the end, the puzzle is guaranteed to be solved, if it was valid, which might be checked at the beginning of the puzzle itself.

Here's the code:
sudoku solver 1.0

 You can checkout my Sudoku Program (Windows version), its licensed under GPLv3, that means you can mess up with the code here (Qt Creator code. All in C++, but may be a bit strange for people who've never used Qt creator.