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? (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. (3) Write the algorithm from scratch in Cython. Does Cython have goto? Cheers, -- Carlo Hamalainen http://carlo-hamalainen.net --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
