A Sudoku Puzzle Solver – attempt 1

July 9, 2013
By

(This article was first published on Econometrics by Simulation, and kindly contributed to R-bloggers)

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:

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"

The results look like this.  You can see that it was not able to solve all of the missing blocks though it is pretty close.
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 his blog: Econometrics by Simulation.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.