[Tutor] 6x6 word square solver too slow

[Tim Peters]

[Jeff Younker]
>> I'd suggest googling for 'trie'.  Tries are method of
>> indexing sets of strings by prefix.

[R. Alan Monroe]
>  Ah, will look it up.

Or you can puzzle it out from the attached program ;-)

> ...
>  In the meantime, my current version is
>  much improved - it caches rejects, so that if one word starting with
>  'ab' fails, it doesn't bother testing any further words starting with
>  'ab'. Also I started using psyco on it.

A better algorithm is what's really needed, and that often means
simpler.  The attached strives for the simplest possible code in the
recursive workhorse function (`_extend()`), and that implies trying to
place only one letter at a time, instead of trying to place an entire
word in one gulp.  You might think that has to be slower, but check it
out:  on my box this runs about 40 times faster than the program you
attached (but not using psyco in either case:  pscyo can't be used
usefully with my program, because its solver is a generator function
and psyco gives up when it sees a generator).  For example, 11.8
seconds versus 552 given seed "enigma", 44 vs 1805 given seed
"serene", and 0.66 versus 30 given seed "python".

It's an interesting problem, and I'm curious to see whether someone
has a faster approach than this.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: wsquare.py
Type: text/x-python
Size: 3320 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/tutor/attachments/20080429/cd5034d0/attachment.py>