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.
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
-~----------~----~----~----~------~----~------~--~---
