Let the hereunder sudoku be the problem to solve.
The easiest and stupidest way of solving it would be to bruteforce the grid.
That is, we would try out all possible numbers in every single cell until a solution comes up. Since there are 56 empty cells to fill, the worst case scenario needs 956 = 2.74*1053 attempts. Assuming a modern CPU is cappable of 300’000 millions of operations per second (MOPS), this takes up to 2.9*1034 years.
Since our planet will probably be dead by that time, it is wise to find another approach.
Constraint Satisfaction Problem
We want to find a solution where is the value of the variable .
Note that in our problem we have 56 variables, each has a domain of allowed values and we want to find a solution .
If we label every variables starting from the top left corner of the grid, going left to right (row by row) and taking into account only the blank cells, must then satisfy the following constraints:
- no duplicate in the set – the first line is composed of unique integers
- no duplicate in the set – the first square is composed of unique integers
A simple algorithm used to solve CSPs, equivalent to the bruteforce approach described above, is generate and test.
We now take a look at a much more efficient method.
A Depth First Search (DFS) based algorithm
Let the root (the first node) of some oriented graph (tree) be the empty set, and let each node be an instantiation of the k first variables, e.g. .
The successor of a node is itself plus an instantiation of the so as to respect all the constraints with .
As shown in the figure below, as soon as a node becomes impossible we discard it (this is called backtracking). This avoids useless exploration of its children.
While this new method seems a little faster, its running time is still exponential in the number of variables. We can add two heuristics to complete our algorithm.
Adding the Forward Checking heuristic
The above method doesn’t discard nodes as soon as they become logically impossible.
Indeed, while all the constraints affecting the first variables might hold, it is likely that some other constraint , is already broken.
As an example of such a case, consider 10 variables. We require the 9 first to have different values, and the 10th to be strictly greater than all the others. Think of all the paths with 9 instantiated variables with different values that are discarded. What a waste.
In the light of this fact we can optimize our algorithm with the forward checking heuristic.
- Add a label (a set) to each variables. Initialize it to the variable’s domain.
- At each instantiation, remove from the label of uninstantiated variables all the values that are inconsistent with this instantiation.
- As soon as a variable’s label becomes empty, we know that the current instantiation isn’t possible. Go back.
Adding the Dynamic Variables Ordering (DVO) heuristic
At each step of the search, sort the variables by label sizes. Instantiate the variable with the smallest label size.
The gain in speed in intuitive, and we no longer need backtracking.
The algorithm having been fully explained, let’s code!
I give the complete source code on github.
Here is the result:
- CS-330 EPFL
- Faltings Boi, and Michael Schumacher. L’intelligence Artificielle Par La Pratique. Lausanne: Presses Polytechniques Et Universitaires Romandes, 2009
12 thoughts on “Automatic sudoku solver”
Great job my friend!
Keep on searching and working!
Gonna be good stuff
A round of applause for your post.Really thank you! Wasner
These are truly wonderful ideas in about blogging. You have touched some nice points here.
Any way keep up wrinting.
Excellent web site you’ve got here.. It’s difficult to find quality writing like yours nowadays.
I really appreciate individuals like you! Take care!!
I’m pretty pleased to find this page. I need to to thank you for your time due
to this fantastic read!! I definitely liked every bit
of it and I have you bookmarked to check out new stuff in your blog.
Thanks a lot for sharing this with all of us you actually understnd what
you are talking approximately! Bookmarked. Kindly also seek
advice from my site =). We can have a link alternate agreement among us
My brother recommended I might like this website. He was totally right.
This post actually made my day. You cann’t
imagine simply how much time I had spent for this info! Thanks!
It is actuallyy a great and helpful piece of info.
I’m glad that you just shared this helpful info with us.
Please stay uus up to date like this. Thank you for sharing.
It’s in reallity a great and useful piece of information. I
am happy that you just shared this useful info with us.
Please stay us informed like this. Thanks for sharing.
Do yoou have any video of that? I’d love to find out more
An outstanding share! I’ve just forwarded this onto a friend who has been conducting a little research on this.
And he actually bought me dinner simply because I stumbled upon it for him…
lol. So allow me too reword this…. Thanks forr the meal!!
But yeah, thanx for spending time to discuss this topic here on your weeb site.
Heya i amm for the first time here. I found this board and I
find It really useful & it helped me out a lot. I hope to give something back and aid
others like youu helped me.