]> granicus.if.org Git - python/commit
Added a non-recursive implementation of conjoin(), and a Knight's Tour
authorunknown <tools@python.org>
Wed, 4 Jul 2001 22:11:22 +0000 (22:11 +0000)
committerunknown <tools@python.org>
Wed, 4 Jul 2001 22:11:22 +0000 (22:11 +0000)
commit31569561fdba94cce39a55a1e033755d06ee8640
treeeb9ed6ae3bce4bd5041a0ca419b0526532fb4033
parenta5aa0b5261314ea0d5675de6aab48a0db37ce316
Added a non-recursive implementation of conjoin(), and a Knight's Tour
solver.  In conjunction, they easily found a tour of a 200x200 board:
that's 200**2 == 40,000 levels of backtracking.  Explicitly resumable
generators allow that to be coded as easily as a recursive solver (easier,
actually, because different levels can use level-customized algorithms
without pain), but without blowing the stack.  Indeed, I've never written
an exhaustive Tour solver in any language before that can handle boards so
large ("exhaustive" == guaranteed to find a solution if one exists, as
opposed to probabilistic heuristic approaches; of course, the age of the
universe may be a blip in the time needed!).
Lib/test/test_generators.py