Background
It was a weekend a few weeks ago when my youngest child saw a sudoku in the paper and wanted to solve it. It was a hard one. And when they are hard I can't keep it all in the head and need to write remaning possible numbers down, but most often I don't find room for that. And for hard sudokus you sometimes have to guess for a number and try that out. When that guess turns out to be wrong, it is no fun at all to backtrack to how the sudoku board looked like before the guess. Both problems can be solved by a computer though! :)
Last time I wrote a sudoku solver was back in 2006 when learning Ruby. I've looked in all my stashes for that code, but it seems to be lost forever. This time the language that I've been looking at besides C# was Python, but so far I hadn't written anything else than short exercises, so it seemed like a good fit to try using it for a small project like this.
I don't even dare to google for sudoku solvers, there probably exist thousands of them, but I want to do this small project in my own little bubble.
Used techniques
Knockout
This is what the board looks like. The nine squares on the board will be called "big squares", and the dots represents the squares that will be called just "squares" or "small squares".
In this example the user has entered two known values, a 9 and a 5.
When running the solver in knockout mode it will knock out the known values from the list of possible values for all other squares. In the example below the value 9 has been knocked out from all squares inside the yellow marking which contains:
1. the big square that the 9 is in,
2. the row the 9 is in
3. and the column the 9 is in
The same goes for the 5, which affect all squares inside the red marking.
When there is a list of numbers in a small square, it is a list of values that still is valid to try out for that small square for solving the sudoku. Therefore, the lists of possible values inside the yellow marking all lacks the number nine, and all the lists inside the red marking lacks the number 5. Small squares that are inside both the yellow and red marking lacks both 9 and 5.
When the knockout runs and a value is knocked out from a square which value list suddenly only contains a single value, that square has become solved by the algorithm. Another round of knockout will be run for that square so its new value will be knocked out from all the squares the solved square affects.
Find unique value
When no more squares can be solved using the knockout technique, the next thing to look for is a list which contains a value that is unique in its big square. In the example in the image below, the square inside the red marking is the only square inside its big square (yellow) that still has the value 7 as a possible value. Therefore the square can be solved with that value and might kick off a new round of knockouts. This example won't though
Brute force
When no more can be done by the other two techniques, it's guessing time. For this, the solver goes looking for the first square with the lowest count of remaining possible numbers. In the board below it is the square marked with red that contains possible numbers 3 and 7.
The solver will begin to try with the number 3. So it sets the square to that value and then runs the "knockout" and "find unique value" routines.
For this guess the board ends up looking like the board in the top of the image below. This board state is a fail because of the solved numbers the big square in the middle of the bottom row, there are two occurences of the number 8.
That erroneus state makes the solver understand that it has to backtrack to the last guess and try out the other value, in this case number 7.
Some sudokus requires multiple squares to be solved using the brute force routine. In the example above the printout says "Brute forcing 4 squares", which means that three other squares has gotten their value by guessing before the processing of the current square.
The code
The solution is a bit unfocused because I never decided if I wanted to build a complete solver or just a helper that could help us a little bit when trying to solve hard sudokus during the weekends.
Another reason the code might seem strange is that I wanted to investigate the functional side of Python, but didn't get any relevation. Which isn't too strange I just found out, reading the answers in the link below.
Over all I would say that Python isn’t very functional at all, and if you try to force a functional style into python it doesn’t feel very natural, and you will have to break out of it each time you want to use a third party library.
So writing a solver in F# or Haskell might be material for another project, but currently I'm a bit fed up with sudokus :)
Inga kommentarer:
Skicka en kommentar