[This article was first published on Econometrics by Simulation, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
I have programmed up a R based Sudoku problem solver for Sudoku puzzles of that only require simple inference. In these puzzles a solution can be found using only first order inference. This solver can be found at the end of the code located in the git:Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
https://github.com/EconometricsBySimulation/2013-06-14-Sudoku
A puzzle of this form can look like this (generated from the R code on the git)
A solution to this problem can be found using the following steps generated from the solver:
[1] “Round 1 -sub out 1 4 with 4” That is sub out row 1 column 4 with a 4.
[1] “Round 1 -sub out 1 6 with 5”
[1] “Round 1 -sub out 2 7 with 5”
[1] “Round 1 -sub out 2 8 with 3”
[1] “Round 1 -sub out 2 9 with 8”
[1] “Round 1 -sub out 3 5 with 9”
[1] “Round 1 -sub out 3 9 with 2”
[1] “Round 1 -sub out 4 7 with 2”
[1] “Round 1 -sub out 5 5 with 4”
[1] “Round 1 -sub out 5 8 with 6”
[1] “Round 1 -sub out 6 1 with 2”
[1] “Round 1 -sub out 6 6 with 9”
[1] “Round 1 -sub out 7 5 with 5”
[1] “Round 1 -sub out 8 9 with 9”
[1] “Round 1 -sub out 9 1 with 3”
[1] “Round 1 -sub out 9 2 with 2”
[1] “Round 1 -sub out 9 3 with 4”
[1] “Round 1 -sub out 9 6 with 1”
[1] “Round 1 -sub out 9 9 with 7”
[1] “Round 2 -sub out 1 1 with 1”
[1] “Round 2 -sub out 1 2 with 3”
[1] “Round 2 -sub out 1 3 with 2”
[1] “Round 2 -sub out 2 1 with 7”
[1] “Round 2 -sub out 3 1 with 6”
[1] “Round 2 -sub out 3 2 with 5”
[1] “Round 2 -sub out 3 8 with 1”
[1] “Round 2 -sub out 4 2 with 8”
[1] “Round 2 -sub out 4 4 with 6”
[1] “Round 2 -sub out 4 8 with 9”
[1] “Round 2 -sub out 4 9 with 5”
[1] “Round 2 -sub out 5 2 with 7”
[1] “Round 2 -sub out 5 3 with 5”
[1] “Round 2 -sub out 5 4 with 2”
[1] “Round 2 -sub out 5 9 with 3”
[1] “Round 2 -sub out 7 1 with 8”
[1] “Round 2 -sub out 7 2 with 9”
[1] “Round 2 -sub out 7 3 with 6”
[1] “Round 2 -sub out 8 4 with 8”
 |
| Interestingly, I think this puzzle has two potential solutions. |
This solver is not at the level I wanted it to be at. I can imagine two more levels of inference that it could handle: one in which the solution uses secondary inference information. Such as knowing that if it chooses a particular value the other block cannot be filled with that value. This I call a type 2 and finally a guess and check method which I call a type 3. The guess and check method should be easy to program but have the difficulty that if there are many squares not solved by the previous methods, it will potentially bog down the machine as it has to check a near infinite number of potential solutions.
However, there should be very few puzzles in which guess and check would be required since those puzzles would be even harder for most people to solve than they would for an algorithm.
I am not satisfied with this solution but I wanted to post this because I had worked it out a few weeks ago and my real work is calling so I am not sure when I will get back to this.
To leave a comment for the author, please follow the link and comment on their blog: Econometrics by Simulation.
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.