Series: Constraint Solver in Julia
This is part 4 of the series about: How to build a Constraint Programming solver?
Did you think about how humans solve sudokus?
At the moment we are simply removing values which are already set but what about a number which only exists once in possible values.
This is the example after the first post and in the penultimate row we have the following:
We clearly can set the value to 6 in the second block as we know that there has to be a six in the row (and also in the block) and it’s the only choice for the six.
Let’s have a look at another case in this grid. The second row is quite interesting as well:
Here we have the possibilities 5 & 6 on the right block which means that we can’t use 5 or 6 in the left part which fixes the left most value to 4 and the next to 9. We still don’t know whether it’s 5 and then 6 in the last block or 6 and 5 but we fixed two additional values.
Now the problem with the first part is a bit that maybe the 6 doesn’t need to be fixed if we just want 9 values out of 10 or something (if we don’t solve sudokus). We could check whether the number of values matches the number of indices.
The second one is not straightforward to implement I think and there a more thinks we could fix by doing some more reasoning.
In this post we will do some graph theory reasoning instead. Some of you might have read the post about Sudoku already but as this is a new series I want to explain it here again but will use the same visualizations as before.
I write about the implementation details in the end which are a bit messy at the moment in my opinion but not sure yet how to make it easier and being still fast or even faster so if you have some ideas 😉 (actually writing it down in this blog made it less messy and faster :D)
Okay let’s dive into graph theory: First of all want we want to do:
- Create a graph where we connect our cells to the possible values we have in them.
The first row shows us the indices of the cells labeled a-i and the bottom row represents the values we have in general.
We might have some fixed values:
and then we add all the other edges which are possible:
these are the possibilities of the third row in our sudoku:
I know the graph looks a bit full but we can add some color:
The green arrows show one possible matching. Now as mentioned several times in this series we always want to know as fast as possible if the current search space is infeasible or if we still…