On Sat, 23 Feb 2008, William Stein wrote:
>
> On Sat, Feb 23, 2008 at 12:46 PM, <[EMAIL PROTECTED]> wrote:
>>
>>
>>
>>
>> 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.
>
> Here's an example of using an "evil trick" Tom just suggested
> to me to make a goto directly in Cython. NEVER REALLY
> DO THIS! This is for your amusement only.
Dirty, William. I can't believe you blame this on me -- that was all Robert's
fault. Anyway. I've co-opted Ajanki's framework, and have rewritten the core
of the search algorithm to be iterative. And, without a single goto! I'm
going to test this some more, and update my patch for #2271 in a few hours.
Seems to work flawlessly, and I can color K_22 in less than 8 seconds (not
impressive, no, except that previously, attempting to color K_14 exceeded
recursion limit).
>
>
> cdef extern from "stdio.h":
> void goto "goto out; //"()
> void receive "out: //"()
>
> print "1"
> goto()
> print "2"
> receive()
> print "3"
>
> ########################
>
> This outputs:
>
> 1
> 3
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
