Tuesday, July 9, 2013

A Sudoku Puzzle Solver - attempt 1

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.

No comments :

Post a Comment