Idiomatic backtracking in Python
rosuav at gmail.com
Mon Jan 26 02:45:03 CET 2015
On Mon, Jan 26, 2015 at 12:31 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
> Backtracking means the part of depth-first traversal where you retreat
> to the parent node. If you implement your traversal with a recursive
> function, backtracking means — more or less — a return from the
But possibly you need to return from N levels, not just one. Imagine
you're traversing a directory tree using a simplistic recursive
for d in subdirs(dir): traverse(d)
for f in files(dir):
if file_size(f) > 1024*1024*1024: skip this entire branch of the tree
Obviously you have to define the branch somehow, but there are plenty
of times when you might want to break out of "everything up to here".
How do you define that? How do you return lots of levels all at once?
I remember facing this exact problem in trying to solve a particular
piece-layout puzzle; if I discovered an impossible situation, I could
actually discard at least two or three levels of recursion all at
once, because there's no way that the situation could become
un-impossible within those levels. Can't remember how I ended up
dealing with that... I think I got naughty and used a global variable.
More information about the Python-list