Soduku

[Jack Diederich]

On Wed, Feb 15, 2006 at 06:56:56PM -0800, Raymond Hettinger wrote:
> [Jack Diederich]
> > Is my math off or does 27ms mean 0.027 seconds? On my laptop (1.3GHz)
> > an empty python program takes 10ms to run (0.010 secs).  I ask out of
> > vanity, my own solver takes .15 seconds to run (20 seconds for a 16x16 grid).
> 
> Comparisons for individual puzzles are likely to be meaningless.  Any
> algorithm is at some point forced to try out assumptions from many
> possiblities.  A lucky or unlucky string of guesses would throw-off the
> comparisons.  Ideally, they should run hundreds of sample puzzles and
> include a good many that involve making mulitple levels of assumptions.
>  Some of the easy puzzles solve readily without a depth-first search
> (so a good chuck of the code may go unexercised).  Another comparison
> issue is the choice of data structures for input, working data, and
> output -- the accessing differing structures may cloud the comparison
> of difference algorithms.

True, especially for 9x9 grids.  I can make my solver go 'faster' by
eliminating the more complicated heuristics. There is extra overhead in
setting them up but the puzzle doesn't have to resort to them.  For 16x16
boards the extra bookkeeping reduces the search space dramatically.

> FWIW, my version is listed on ASPN:
>     http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/473893

Short and concise but .. what, no sets?!  
I used sets initially (each cell is a set object of int values) and 
was pleasantly surprised how fast it was.  Not leaving well enough alone
I wrote a C based set-alike that uses bit vectors to represent small
int sets (each bit is 0,1,2 .. sizeof(unsigned long)*7 - 1).
Despite the fact that or/and/sub are simple bit operations it is 
only 1/3rd faster than regular sets.  It doesn't cache and reuse objects
like sets; I'd like to think that is why it isn't faster still.

To compare different implementations (regular set vs bitset) of the same
strategy you have to record and playback any random-ish parts like taking
the first value of list(set-thing)[0].

I've been meaning to do a writeup. I'll try harder to find the time.

-Jack