Path: csiph.com!usenet.pasdenom.info!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.013 X-Spam-Evidence: '*H*': 0.97; '*S*': 0.00; 'that?': 0.05; 'tree': 0.05; 'subject:Python': 0.06; 'discard': 0.07; 'plenty': 0.07; 'function,': 0.09; '\xe2\x80\x94': 0.09; 'cc:addr:python-list': 0.11; 'def': 0.12; 'jan': 0.12; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'levels,': 0.16; 'node.': 0.16; 'somehow,': 0.16; 'variable.': 0.16; 'wrote:': 0.18; 'obviously': 0.18; 'trying': 0.19; 'cc:addr:python.org': 0.22; 'skip': 0.24; 'mon,': 0.24; 'cc:2**0': 0.24; 'define': 0.26; 'possibly': 0.26; 'least': 0.26; 'header:In-Reply-To:1': 0.27; 'message- id:@mail.gmail.com': 0.30; 'once,': 0.31; 'could': 0.34; 'problem': 0.35; "can't": 0.35; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'two': 0.37; 'implement': 0.38; 'branch': 0.38; 'pm,': 0.38; 'how': 0.40; 'skip:u 10': 0.60; 'solve': 0.60; 'break': 0.61; 'entire': 0.61; "you're": 0.61; 'times': 0.62; 'become': 0.64; 'more': 0.64; 'levels': 0.65; 'situation': 0.65; 'within': 0.65; '26,': 0.68; 'discovered': 0.83; '2015': 0.84; 'naughty': 0.84; 'to:none': 0.92; 'imagine': 0.93 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:cc :content-type:content-transfer-encoding; bh=ZtH7OX/SOI39rK93Kl4sev4dCeLVqe+YC4keqv/9AE0=; b=EIxb3DN0KckoEKLxaUKXr97F4LTmLb79hURJCuxAnygLOrcgOZ2n81AbHfKxUOvpzM aqLMF5q94SlvQKL7qSssLwkMn8MDC8xDRJTLqeX83Zx5ovMDnqhbxbFkluynzh8243DK o8SLyqqszHifJFHuwqNkZljmxlzpC6m2himJGfXJmiygRhxoxFSg4DHfq6/jJrBmQzD3 sPw8Sl9R0txvzXWT6wGal7lA+z68/JPDTf43mCvu4K8Ei39Mc4Nua6sVKtDsJQn3H37D uKt0KihNfc3fCXuU+FP5SqLI9pM5+j8JCfMf7W+Fe3xLwIkNCBED1Ky+DTTXrCVsSo6K NCcQ== MIME-Version: 1.0 X-Received: by 10.50.18.108 with SMTP id v12mr14043667igd.34.1422236703454; Sun, 25 Jan 2015 17:45:03 -0800 (PST) In-Reply-To: <87bnlml44b.fsf@elektro.pacujo.net> References: <87bnlml44b.fsf@elektro.pacujo.net> Date: Mon, 26 Jan 2015 12:45:03 +1100 Subject: Re: Idiomatic backtracking in Python From: Chris Angelico Cc: "python-list@python.org" Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 28 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1422236712 news.xs4all.nl 2922 [2001:888:2000:d::a6]:41646 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:84586 On Mon, Jan 26, 2015 at 12:31 PM, Marko Rauhamaa 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 =E2=80=94 more or less =E2=80=94 a return fr= om 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 tr= ee 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. ChrisA