[Talin] > I've been using generators to implement backtracking search for a while > now. Unfortunately, my code is large and complex enough (doing > unification on math expressions) that its hard to post a simple > example. So I decided to look for a simpler problem that could be used > to demonstrate the technique that I am talking about. > > I noticed that PEP 255 (Simple Generators) refers to an implementation > of the "8 Queens" problem in the lib/test directory. Looking at the > code, I see that while it does use generators, it doesn't use them > recursively.
In context, the N-Queens and MxN Knight's Tour solvers in test_generators.py are exercising the conjoin() generators in that file. That's a different approach to backtracking search, with some nice features too: (1) it uses heap space instead of stack space; and, (2) it's easy to run entirely different code at different levels of the search. #2 isn't well-illustrated by the N-Queens solver because the problem is so symmetric, although it is used to give the code for each row its own local table of the board lines used by the squares in that row. That in turn is a major efficiency win. The Knight's Tour solver makes more obvious use of #2, by, e.g., running different code for "the first" square than for "the second" square than for "the last" square than for "all the other" squares. That doesn't require any runtime test-and-branch'ing in the search code, it's set up once at the start in the list of M*N generators passed to conjoin() (each square gets its own generator, which can be customized in arbitrary ways, in advance, for that square). > As an alternative, I'd like to present the following implementation. If > you compare this one with the one in lib/test/test_generator.py you > will agree (I hope) that by using recursive generators to implement > backtracking, the resulting code is a little more straightforward and > intuitive: Since "straightfoward and intuitive" weren't the goals of the test_generators.py implementations, that's not too surprising ;-) > ... -- http://mail.python.org/mailman/listinfo/python-list
