Idiomatic backtracking in Python

[Chris Angelico]

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