Path: csiph.com!usenet.pasdenom.info!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed1a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Tue, 03 Feb 2015 16:16:02 -0500
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Idiomatic backtracking in Python
References: <ma3itj$ol6$1@news.albasani.net> <mailman.18136.1422232323.18130.python-list@python.org> <87bnlml44b.fsf@elektro.pacujo.net> <CAPTjJmr5Bp7oi9mNg9TqGwkXng38SSik+q7xcWfHuRXjgP_fgg@mail.gmail.com>
In-Reply-To: <CAPTjJmr5Bp7oi9mNg9TqGwkXng38SSik+q7xcWfHuRXjgP_fgg@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.18441.1422998174.18130.python-list@python.org>
Lines: 38
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:85173

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