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

Groups > comp.lang.python > #85181

Re: Idiomatic backtracking in Python

Show all headers | View raw

On Wed, Feb 4, 2015 at 8:16 AM, Dave Angel <davea@davea.name> wrote:
>> 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.

That's true of most problems. I may have to go dig up the code I had,
but I believe the basic structure was something along the lines of
"place piece in available space, recurse to place piece in each
remaining available space". Sometimes, attempting to fill one space
would prove that the piece that _created_ that space couldn't possibly
go there, so it would do a jump back up a few levels of recursion.
Definitely an unusual situation, but not impossible.

ChrisA

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