Friday, June 14, 2013

Sudoku Automation Solver Challenge - R

On a recent flight I was bored waiting for the plane to land and I tried out the electronic sudoku game that they had offered.  I found the game surprisingly interesting as I realized that it is far more entertaining when you cannot use paper or pencil to augment the cognitive solution seeking process.  In addition, having your score based on your time presented an objective challenge and measure to test yourself against.

Figure 1:a sample Sudoku grid
After that I decided to design a Sudoku generator.  Which I have included:

https://github.com/EconometricsBySimulation/2013-06-14-Sudoku

It has been an entertaining exercise figuring out methods to produce matrices that conform to the specifications of a Sudoku table.  That is a table which distributes sets of 1 to 9 distributed both horizontally, vertically, and in a 3x3 grid without duplicates for all squares in a 9x9 grid.

Figure 2: Ultimate Sudoku
You can see from the R script (and the grid produced by it figure 1) that I am able to accomplish this very easily through a randomized guess and check process (with the computer finding a solution in 1 in 50-500 attempts) that is capable of drawing nearly an infinite number of grids (of course there is a finite though very large number of possible grids).

I have also made a variant that I call Ultimate Sudoku which conforms to Sudoku rules and also adds one more rule to the grid in which each position in a 3x3 set is part of a set of all other 3x3 sets in which there can be no duplicate entries from the set.  That is for instance that the first square in a 3x3 grid cannot have duplicate entries with any of the other first squares in the other grid.  An example table that I generated using R is figure 2.

I don't think it is likely that Ultimate Sudoku will take off but for those hard core Sudoku players this variate would present an option that would allow for more challenging games since players must keep track of four overlapping sets of elements rather than 3.  Under this set up effectively more spaces could be made blank.  The R script is also capable of generating these though it is a bit more challenging to find grids that conform to all four rules (usually between 1 out of 4-10 thousand attempts).

I have also defined a function to strategically remove values from the plotted grid so that players are faced with an incomplete grid.  I have been able to vary the difficulty of these grids as well by specifying the average number of missing elements (from the set of 1 through 9) for each grid value.  You can see examples of problem grids I have generated in figures 3 and 4.

Figures 3 and 4

What I realized though was what my system is still not perfect because it is possible that I can come up with grids which might not have solutions which would present a problem.  What is really needed is an algorithm which is capable of doing what Sudoku players are capable of doing, that is solve the tables.  So rather that taking the next step designing an algorithm to solve my sample tables I thought that perhaps some of my readers out there might be interested in attempting to design an algorithm to solve these potential Sudoku tables and identify which ones are not feasible.

So, that is the challenge!  It should be easy to run the code an generate and map the tables using the Git.

No comments :

Post a Comment