Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #85173

Re: Idiomatic backtracking in Python

Show key headers only | View raw

On 01/25/2015 08:45 PM, Chris Angelico wrote:
> On Mon, Jan 26, 2015 at 12:31 PM, Marko Rauhamaa <marko@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
>> function.
>
> But possibly you need to return from N levels, not just one. Imagine
> you're traversing a directory tree using a simplistic recursive
> algorithm:
>
> def traverse(dir):
>      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.
>

When I've done things like that, there was no need to do a "return 
multiple".  You just return, and your caller happens to be a the end of 
his loop, so he returns also.

Classic example of this is the 8 queens puzzle.  Each level is going to 
examine one row, and once there are no places that aren't yet attacked, 
it simply returns.


-- 
DaveA

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Idiomatic backtracking in Python Johannes Bauer <dfnsonfsduifb@gmx.de> - 2015-01-25 21:15 +0100
  Re: Idiomatic backtracking in Python Ian Foote <ian@feete.org> - 2015-01-25 20:51 +0000
    Re: Idiomatic backtracking in Python Rustom Mody <rustompmody@gmail.com> - 2015-01-25 18:41 -0800
      Re: Idiomatic backtracking in Python Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2015-01-26 09:21 +0200
        Re: Idiomatic backtracking in Python Rustom Mody <rustompmody@gmail.com> - 2015-01-25 23:28 -0800
  Re: Idiomatic backtracking in Python Ben Finney <ben+python@benfinney.id.au> - 2015-01-26 11:32 +1100
    Re: Idiomatic backtracking in Python Marko Rauhamaa <marko@pacujo.net> - 2015-01-26 03:31 +0200
      Re: Idiomatic backtracking in Python Chris Angelico <rosuav@gmail.com> - 2015-01-26 12:45 +1100
      Re: Idiomatic backtracking in Python Dave Angel <davea@davea.name> - 2015-02-03 16:16 -0500
      Re: Idiomatic backtracking in Python Chris Angelico <rosuav@gmail.com> - 2015-02-04 09:29 +1100
  Re: Idiomatic backtracking in Python MRAB <python@mrabarnett.plus.com> - 2015-01-26 00:43 +0000
  Re: Idiomatic backtracking in Python Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-01-26 08:06 +0000
  Re: Idiomatic backtracking in Python sjmsoft@gmail.com - 2015-01-27 04:48 -0800

csiph-web