A Pattern So Grand and Complex! (Part 1)


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!

But before you start, you need to know the rules and some solving strategies and lingo of Sudoku !

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.

Generate positions with Pharo Smalltalk

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).

Generate sudoku constraints from Pharo Smalltalk

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.

creation of everything needed

Now that we’re done, let’s see how it works for this grid:

sudoku_grid_01

To solve this, we have to execute this query :

solution for grid 1

Here’s what the EXPLAIN had to say:

explain no 1 for grid 1

explain no 2 for grid 1

Voilà!

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!

Enjoy!

About these ads
Published in: on December 15, 2010 at 22:55  Leave a Comment  

The URI to TrackBack this entry is: http://myfavoriteheadache.wordpress.com/2010/12/15/a-pattern-so-grand-and-complex-part-1/trackback/

RSS feed for comments on this post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: