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:
- 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.
I first tested on a simple news paper problem.
After a single guess I can find the solution to be:
I then tried a 17 given problem from Wolfram Alpha.
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:
unfortunately I seem to have also spat out another valid solution:
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