The Spirit of Radio


Nothing’s like good music when you’re coding…

97.7 HTZ-FM

Published in: on January 17, 2011 at 01:25  Leave a Comment  

A Certain Measure Of Innocence


Slowly getting there… The sign of eth is rising in the air!

Published in: on January 12, 2011 at 23:32  Leave a Comment  

The Sign Of Eth Is Rising In The Air


Brief pause of that Sudoku series :  I’m working on my object-relational mapping framework code-named Eth.

It’s vaguely similar to Glorp but much simpler and not as intelligent as Glorp.  This time, the resurrection of my framework is more like… a rewrite from scratch.  It all started on VAST, then I ported it to Dolphin then Squeak and now Pharo.  Hopefully, now I will spend more time writing it than porting it! Also, it will exclusively support Pharo.  I also decided to write some SUnit tests to make sure I can properly handle PostgreSQL, MySQL and Interbase for the first version.  But I am also planning on supporting SQL Server, Oracle, DB2, Access and Firebird.  Eventually!

Besides, I’m also spending quite some time solving mathematical problems at ProjectEuler with Pharo Smalltalk.  Lots of fun!

But stay tuned as I should be back soon with part 2 of that Sudoku article!

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!

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

Finding My Way


I am preparing a series of posts related to Sudoku. I am revisiting the “SQL only” solution I posted somewhere else a long time ago…  This time, we’ll get serious and optimize everything we can!  This lemon will be squeezed to the maximum!

Start your Pharo image (not mandatory since I will provide all necessary SQL scripts) and MySQL server as we’ll try to solve some Sudoku puzzles only with one SQL statement (no stored procedures or functions)!

Part 1 coming soon!

Published in: on December 13, 2010 at 12:53  Leave a Comment  

Worn by Persistence


Let me know what’s your favorite database!

Enter the poll!

Published in: on December 12, 2010 at 02:55  Leave a Comment  

Test For Echo


Tell me what is your favorite headache!

What’s your favorite Smalltalk environment?

Published in: on December 11, 2010 at 21:51  Leave a Comment  
Tags:

Here Again


I’m back in the blogosphere!

This blog will focus on Smalltalk (mostly Pharo, Squeak, Dolphin, VAST and VW), databases (usually MySQL, PostgreSQL, SQL Server, DB2, InterBase and Firebird), algorithms and open source tools.  I’ll throw in some literature, music and mathematics occasionally.

Requirements to enjoy this blog : an interest in problem solving, a database and a Smalltalk environment!

Follow

Get every new post delivered to your Inbox.