The art of simplicity is a puzzle of complexity. (Douglas Horton)
No puzzle looks simpler than a Sudoku. But behind the very few rules of this game hides enormous complexity. It’s now proved that there are 6670903752021072936960 different grids for a standard 9×9 Sudoku. More refinements and subtleties taking symmetries into account have been examined as well as other variants of Sudoku. Solving strategies have been studied inside out, enumerated and refined. Sudoku grids and Latin squares have kept mathematicians busy for a long time and lots of hidden patterns and complex concepts still remain to be discovered. This little game is a treasure island for mathematicians and developers : we only need to dig deep enough and long enough…
This series of posts will only focus on 9×9 standard Sudoku to keep things simple. We’ll try to find a SQL only solution to solve Sudoku puzzles, with no stored procedures, no scripts nor functions : only plain SQL statements! This first article will focus on creating the data we will need for this optimization marathon!
The solution and data representation I came up with is trivial : let’s create all possible permutations for one row and store those in a table and self-join this table 9 times while adding all Sudoku rules constraints to make sure we end up with a valid Sudoku grid. For 9 items, I had to create 9! (362880) rows.
I created the data for all the INSERT statements with a simple Smalltalk script in Pharo.
The constraints were also generated with a Pharo Smalltalk script. This script eliminates all unnecessary clauses and constraints to keep their number to the absolute strict minimum while making sure we would still have valid Sudoku :
1) Eliminate duplicate clauses (for instance, no need to specify (r1.c3 <> r2.c3) and (r2.c3 <> r1.c3), it’s the same thing!) ;
2) Eliminate all rules related to rows (we know that all rows in our positions table are valid Sudoku rows).
Now we’re ready to go! All necessary files used in this article can be found here (1.3 Mb zip file). If you have a problem with the download, contact me and I’ll send you the zip file by email. Look at my “About Me” page for info!
Take note that scripts 3 & 5 might take few minutes to execute!
So we need:
1) create the sudoku database;
2) create the positions table;
3) populate the positions table;
4) create the sudoku_view view with the necessary constraints (sudoku rules)
5) create indexes on the base table positions.
Now that we’re done, let’s see how it works for this grid:
To solve this, we have to execute this query :
Here’s what the EXPLAIN had to say:
Works like a charm! Only 0.39 seconds to solve !
Too easy! Hmmmm !? Unless…
Well, lots of problems (and hopefully… solutions!) ahead but that’s gonna be my next article!