On Sat, 23 Feb 2008, Carlo Hamalainen wrote:
>
> On Fri, Feb 22, 2008 at 8:55 PM, <[EMAIL PROTECTED]> wrote:
>> Arguments for including Ajanki's code:
>> 1) It's the only Python implementation of DLX I've seen.
>> 2) I emailed the author, who happily added the "or later" bit after the
>> GPL2
>> 3) With my Sage Matrix -> DLXMatrix code (plus docstrings to everything
>> I added), the file dlx.py is only 8kB!
>> 4) It will resolve tickets #1311 and #1313
>
> This afternoon I wrote some code to get completions of partial latin
> squares using Ajanki's DLX code (this is basically the same as solving
> a Sudoku puzzle, minus a few constraints because latin squares don't
> have the 3x3 blocks).
>
> I discovered that the main function, dosearch(), uses recursion, and
> Python's recursion limit is reached quite easily (e.g. finding a
> completion of a 16x16 partial latin square blows up). Knuth's original
> implementation in C avoided recursion by using an array to simulate a
> stack, and looping uses goto statements, and so it can be run on quite
> large problem instances. As a side benefit there is no function call
> overhead in the main part of the algorithm.
>
> I have been using my own implementation of DLX in C++ for a while now
> and I've found it very useful, so I'm all for the algorithm getting
> into Sage. I can see a few ways forward:
>
> (1) Rewrite Ajanki's code to avoid the recursion limit. The problem
> here is that Python doesn't have 'goto'. Can the recursion limit be
> dealt with in some other way?
Yes, I've devoted some thought to this -- we can remove the recursion by using
a stack. This shouldn't be too hard. But why do you want a "goto"? That's
like duct-taping your car door shut when the latch works fine.
> (2) Write a wrapper for an implementation in C++. I'm happy to make my
> code GPL and I'm also happy to write a wrapper once I get my head
> around cython/pyrex.
Sweet. I wanted Ajanki's code because it worked out of the box. I modified it
a little so it'd yield solutions rather than using a callback function. Faster
is better.
> (3) Write the algorithm from scratch in Cython. Does Cython have goto?
I'm sitting across from Robert Bradshaw. He said "Gotos are ugly. Well, gotos
are ugly unless you're writing a compiler, and then you need them". So no, no
gotos in Cython.
DLX should be absolutely trivial to implement using a stack instead of
recursion. That should give a huge boost, and there will be no need for gotos.
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
