Solving Sudoku

I was chatting with my manager the other day, just shooting the breeze, and we got on to how he knocked together a python script to prove to his girlfriend that programmatically solving sudoku puzzles is easy.

I disagreed for a moment and then realised I was thinking of generating sudoku puzzles, which we agreed isn't easy.

I had tried to make a sudoku helper app before, to practice MVVM and WPF, but had messed up in some calculation or other. Probably at the point where I was calculating which block a square was in. Anyway I had deleted that one, but my boss had spurred my interest in doing it again.

I'm a better programmer than I was that first time - I understand both WPF and MVVM better now, so this little solver is pretty sweet. (Unless you look at the code.)

It has all the features I need. I can fill in the known numbers, delete mistakes, and click a button to solve the unknowns (once the knowns are in place).
Sometimes you don't even need the button, since the programme eliminates possibilities as you type. One puzzle I tried was solved before I typed in all the known numbers!

So my amazing solver has two simple algorithms doing the solving:

1. Each square has an event that fires when its number of possible values reaches 1, either programmatically or by user intervention. This event is subscribed to by all the squares related to it (row, column, block), and so each related square will remove this value from their possible values list. This can cause a chain reaction of updates, solving the sudoku puzzle when enough knowns are typed in.
2. If elimination alone doesn't do the job then the second algorithm is just a button click away. I might have over thought this one:
1. Create a list of squares that have at least 2 possible values, sorted in ascending order of number of possible values
2. Take the first square and find all the squares in the same block
3. Add theses squares to a checked block list
4. Flatten the lists of potential values into one list
5. Find any unique values in that list
6. If there are any unique values then these represent solved squares so break out of the loop and update the squares related to those values.
7. If there isn't a unique value then repeat 3, 4 and 5 for the row, then the column of the current square.
8. If after that there still isn't a unique value, move onto the next square that hasn't been checked yet.

If at the end of the second algorithm a number hasn't been updated then the programme lets the user know that it needs more knowns, otherwise it starts the second algorithm again until all the squares are filled.

I know what you're thinking. You're thinking that if a user makes a mistake inputting a value, then when they delete it and input a new value the possible values list for the related squares will be wrong. Fear not! Deleting a value fires an event that does the opposite of inserting a value, so things go back to the way they were. Phew!

If you want to look at the code it's on github here: http://github.com/Mellen/SudokuSolver

The code is c#. The project is a Visual Studio 10 project, that runs on the .NET 4.0 framework. It even has a couple of unit tests. Yes, I'm that guy. I unit test toy projects.

The executable is available from github: SudokuSolver1.0.2.zip. It requires .NET version 4.0.

Anyway! This was a fun little diversion. I makes me happy that I got it right the second time.