Polyform Puzzler and a Pythonic Algorithm X

Talks | Submit a talk
Authors David Goodger
Level Intermediate
Topic None of the above
Tags algorithms, data structures, polyforms, puzzles
Summary

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.

Outline

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.

Notes

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.

Profile of the authors

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

Files
No files uploaded. You can upload a file if you are author of this talk.