I am trying to remind myself of a little C++ and have decided the ideal project to do so would be to write a little solver for Sudoku. My aim is, given a board, to find all valid solutions. A solution is valid if each number is present exactly once on each line and row and in each quadrant. There are two ideas that I use: updating the constraints and performing a depth first search.

# Updating the constraints

Given a particular assigned position on the board, no other position on the same row or in the same quadrant is allowed to have that value. I therefore store in an array of 9bits the allowed values for each position. For example, if a particular position is allowed to be in any position its state would be “111111111”. If, however it is allowed to only have a value of ‘1’ or a value of ‘3’ its’ state would be: “000000101”.

There are two particular important states. If a position is not allowed to take any value, then its state will be 0. This means that the board configuration I am considering is not valid. If on the other hand the state has a single true bit, then the position is in a definite state and I can assign that position. So the pseudo code for updating the constraints is:

- UpdateConstraints(AssignedPositions):
- for aPos in AssignedPositions:
- if aPos has not yet been assigned:
- assign aPos
- for neigh in (list of neighbour of aPos):
- unset aPos as possible state of neigh
- if neigh has no possible states left: return -1
- for Pos in AllPositions:
- if Pos has a single state left: GOTO 1
- return 0

# Depth first search

The approach above is not sufficient, as given the initially assigned cells, it is possible for certain positions to still not have a determined state even after updating the constraints. In order to try out all possible states, I perform a depth first search, by creating all board states that differ from the original one by having a single cell occupied and performing the algorithm above.

# Testing

I first tested on a simple news paper problem.

Starting problem:

_____________

|304|610|005|

|708|000|306|

|000|903|400|

_____________

|807|000|510|

|020|705|040|

|600|091|002|

_____________

|480|352|007|

|000|000|900|

|106|009|280|

_____________

After a single guess I can find the solution to be:

_____________

|394|617|825|

|718|524|396|

|562|983|471|

_____________

|837|246|519|

|921|735|648|

|645|891|732|

_____________

|489|352|167|

|273|168|954|

|156|479|283|

_____________

I then tried a 17 given problem from Wolfram Alpha.

_____________

|030|000|900|

|006|000|000|

|000|241|030|

_____________

|000|900|700|

|000|002|004|

|080|070|020|

_____________

|850|000|000|

|090|704|000|

|000|006|001|

_____________

this problem is clearly much much harder. The problem still is solved in a fraction of a second, having tried just 88 guesses with solution:

_____________

|532|768|941|

|416|395|872|

|978|241|635|

_____________

|325|984|716|

|769|512|384|

|184|673|529|

_____________

|853|129|467|

|691|437|258|

|247|856|193|

_____________

unfortunately I seem to have also spat out another valid solution:

_____________

|532|768|941|

|416|593|872|

|978|241|635|

_____________

|325|984|716|

|769|312|584|

|184|675|329|

_____________

|853|129|467|

|691|437|258|

|247|856|193|

_____________

It turns out that a “mathematician’s” Sudoku is different from a regular Jo one. The maths ones are allowed to differ by certain symmetry operations that I do not understand. Still main objective – to brush up on my C++ is achieved! Here is the source code – if you like you can inspect my code here