Polyform Puzzler and a Pythonic Algorithm X

This talk will introduce the concept of polyform puzzles and the Polyform Puzzler project (puzzler.sourceforge.net). Then we'll focus on the evolution of the algorithms used to solve these puzzles, from slow and misguided to naïvely complex through to Pythonic, simple and fast. Finally we'll discuss the choice of algorithms and their implementation in high-level Python.

Introductions of:

• Polyform puzzles (pentominoes, etc.)

• the Polyform Puzzler project (http://puzzler.sourceforge.net)

Detailed discussions of the three approaches used to solve polyform puzzles:

• First was a brute force algorithm with "intelligent" heuristic shortcuts. Having the computer imitate the human approach was complex and slow, but served its purpose as my introduction to Python and the genesis of the Docutils project.

• Next came the 2006 discovery of the Exact Cover problem, Algorithm X, and Dancing Links, in a paper by Donald Knuth. Initially Algorithm X was implemented as a literal translation of the Dancing Links technique, which was much faster and more flexible but the naive implementation was more appropriate for a lower-level language and didn't take advantage of Python's built-in data structures.

• Recently I learned of an alternative approach using a high-level native data structure technique, devised by Ali Assaf: a vastly simplified and Pythonic implementation of Algorithm X. The simplicity also brought speed improvements.

The talk will conclude with some rules of thumb and ramifications of language constructs on algorithm and implementation choices. When programming in Python, the built-in data structures should be used to their fullest.

None of the "Topic" choices suited. Please add "Algorithms and Data Structures" as a choice if possible.

I would prefer 45 minutes but I can do this talk in 30 minutes instead, if that helps scheduling.

David Goodger is a full-time Python programmer and consultant working in the financial sector, founder and architect of the Docutils project and reStructuredText, an editor of the Python Enhancement Proposals (PEPs), chair of the 2008 and 2009 US PyCon conferences, and a member of the Python Software Foundation. David was a Director of the Python Software Foundation from 2006 to 2009. David lives in Canada near Montreal with his wife and two children.

Home page: http://python.net/~goodger Blog: http://www.artima.com/weblogs/index.jsp?blogger=goodger