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

Groups > comp.lang.python > #84578 > unrolled thread

Idiomatic backtracking in Python

Back to article view | Back to comp.lang.python

Contents

  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

#84578 — Idiomatic backtracking in Python

Hi folks,

I have a problem at hand that needs code for backtracking as a solution.
And I have no problem coding it, but I can't get rid of the feeling that
I'm always solving backtracking problems in a non-Pythonic
(non-idiomatic) way. So, I would like to ask if you have a Pythonic
approach to backtracking problems? If so, I'd love to hear your solutions!

Cheers,
Johannes

-- 
>> Wo hattest Du das Beben nochmal GENAU vorhergesagt?
> Zumindest nicht öffentlich!
Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
 - Karl Kaos über Rüdiger Thomas in dsa <hidbv3$om2$1@speranza.aioe.org>

[toc] | [next] | [standalone]

#84580

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi,

I think a very idiomatic way to implement backtracking is using a
recursive generator (python 3):

def backtrack_solver(data=None):
    if data is None:
        yield from backtrack_solver(data=initial_data)

    if cannot_be_valid(data):
        return

    if matches_condition(data):
        yield data
        return

    for new_data in process(data):
        yield from backtrack_solver(new_data)

This generator will yield valid solutions to a suitably defined problem.

`initial_data`, `cannot_be_valid`, `matches_condition` and `process`
should be replaced with appropriate implementation for your problem.

For example, a sudoku solver could be fit to this by accepting a
partially solved grid as the `data` parameter.

`cannot_be_valid` would now detect grids that have, say, two `1`s in a
row or any other invalid grid state and exit.

`matches_condition` would detect a fully solved grid.

`process` would produce new grids with more cells filled in than the
current grid.

`initial_data` wouldn't be strictly necessary here, but you could use
it for an example grid. It could also be an empty grid, and the solver
would then yield all valid grids.

Regards,
Ian F

On 25/01/15 20:15, Johannes Bauer wrote:
> Hi folks,
> 
> I have a problem at hand that needs code for backtracking as a
> solution. And I have no problem coding it, but I can't get rid of
> the feeling that I'm always solving backtracking problems in a
> non-Pythonic (non-idiomatic) way. So, I would like to ask if you
> have a Pythonic approach to backtracking problems? If so, I'd love
> to hear your solutions!
> 
> Cheers, Johannes
> 

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQEcBAEBAgAGBQJUxVc3AAoJEODsV4MF7PWzO+sH/jaz0Dc7Hs9LkbB8g6//A7pK
bxBeFSVtmvaHynASg2PRAzSAC4dty5R52myPoXB3Hdf+otTjBUjOyA7k5j+HCDum
TeJJSUFwOFQxr3yRtXcYoct+xYGBAGRqjT0oiGJMFYp5dLPXmHsAv10KIr3HcOo4
TgqQ9XtyMw60Tmx1ZJ/pj0xOPtrr5PUxe0bwRC5bRycDS943s+UJ/o42DhnBtkZp
h6kkqsZsAL27i0hZrqBEfWMaIHbY9DZNzA9PYyYEl/pzvtB0tpN6ENrxTQFbBNeE
SZoEz9AdcUr9D0ej3HaTgmbT/ivl0op4xQdnpp75uRnGpaH5LlssEGbWQsmRwsY=
=Jpwv
-----END PGP SIGNATURE-----

[toc] | [prev] | [next] | [standalone]

#84588

On Monday, January 26, 2015 at 2:21:34 AM UTC+5:30, Ian Foote wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Hi,
> 
> I think a very idiomatic way to implement backtracking is using a
> recursive generator (python 3):
> 
> def backtrack_solver(data=None):
>     if data is None:
>         yield from backtrack_solver(data=initial_data)
> 
>     if cannot_be_valid(data):
>         return
> 
>     if matches_condition(data):
>         yield data
>         return
> 
>     for new_data in process(data):
>         yield from backtrack_solver(new_data)
> 
> This generator will yield valid solutions to a suitably defined problem.
> 
> `initial_data`, `cannot_be_valid`, `matches_condition` and `process`
> should be replaced with appropriate implementation for your problem.
> 
> For example, a sudoku solver could be fit to this by accepting a
> partially solved grid as the `data` parameter.
> 
> `cannot_be_valid` would now detect grids that have, say, two `1`s in a
> row or any other invalid grid state and exit.
> 
> `matches_condition` would detect a fully solved grid.
> 
> `process` would produce new grids with more cells filled in than the
> current grid.
> 
> `initial_data` wouldn't be strictly necessary here, but you could use
> it for an example grid. It could also be an empty grid, and the solver
> would then yield all valid grids.
> 
> Regards,
> Ian F
> 
> On 25/01/15 20:15, Johannes Bauer wrote:
> > Hi folks,
> > 
> > I have a problem at hand that needs code for backtracking as a
> > solution. And I have no problem coding it, but I can't get rid of
> > the feeling that I'm always solving backtracking problems in a
> > non-Pythonic (non-idiomatic) way. So, I would like to ask if you
> > have a Pythonic approach to backtracking problems? If so, I'd love
> > to hear your solutions!
> > 
> > Cheers, Johannes

To add to Ian:

The classic way of doing it in a functional framework is called:
"Replace failure by list of successes"

https://rkrishnan.org/files/wadler-1985.pdf

The things that have to go into it are
1. Extensive use of list comprehensions
2. Lazy lists

Just change in the above 'list' to 'generator'
and more or less it should work in python

More or less that means when you have a comprehension
[expr for x in list2 for y in list2 etc]

change the '[]' to '()'
and recursively change the list1 list2 to gen1 gen2

Some nuisances that bug me (or I dont know how to handle):

1. Singleton
   [val] becomes (x for x in [val])  (Hoo Boy!)

   Or 
   def single_val(): yield val

2. Nice syntax like list +

Compare [1] + [2]
with

>>> from itertools import chain
>>> a = (x for x in [1])
>>> b = (x for x in [2])
>>> list(chain(a,b))
[1, 2]

Of course it looks worse because the (syntax) overhead of
jumping between lists and generators overwhelms in this trivial case

[toc] | [prev] | [next] | [standalone]

#84591

Rustom Mody writes:

> To add to Ian:
> 
> The classic way of doing it in a functional framework is called:
> "Replace failure by list of successes"
> 
> https://rkrishnan.org/files/wadler-1985.pdf
> 
> The things that have to go into it are
> 1. Extensive use of list comprehensions
> 2. Lazy lists
> 
> Just change in the above 'list' to 'generator'
> and more or less it should work in python
> 
> More or less that means when you have a comprehension
> [expr for x in list2 for y in list2 etc]
> 
> change the '[]' to '()'
> and recursively change the list1 list2 to gen1 gen2
> 
> Some nuisances that bug me (or I dont know how to handle):
> 
> 1. Singleton
>    [val] becomes (x for x in [val])  (Hoo Boy!)
> 
>    Or 
>    def single_val(): yield val

It's just one def:

def sing(*args):
   for arg in args:
       yield arg

Or not even that: iter((val,)).

But see below at the end.

> 2. Nice syntax like list +
> 
> Compare [1] + [2]
> with
> 
> >>> from itertools import chain
> >>> a = (x for x in [1])
> >>> b = (x for x in [2])
> >>> list(chain(a,b))
> [1, 2]
> 
> Of course it looks worse because the (syntax) overhead of jumping
> between lists and generators overwhelms in this trivial case

Yes, one wouldn't jump back and forth so much. Just collect the result
at the end.

>>> list(chain(sing(3,1,4), sing(1), sing(5,9,2,6)))
[3, 1, 4, 1, 5, 9, 2, 6]

>>> list(chain(sing(3,1,4,1), sing(), sing(5,9,2,6)))
[3, 1, 4, 1, 5, 9, 2, 6]

And it gets better: chain takes lists! And tuples! For those who like
their brackets round:

>>> tuple(chain((3,1,4,1), (), (5,9,2,6)))
(3, 1, 4, 1, 5, 9, 2, 6)

>>> set(chain((3,)))
{3}

>>> list(chain(()))
[]

So chain does it all.

[toc] | [prev] | [next] | [standalone]

#84592

On Monday, January 26, 2015 at 12:52:04 PM UTC+5:30, Jussi Piitulainen wrote:
> Rustom Mody writes:
> 
> > To add to Ian:
> > 
> > The classic way of doing it in a functional framework is called:
> > "Replace failure by list of successes"
> > 
> > https://rkrishnan.org/files/wadler-1985.pdf
> > 
> > The things that have to go into it are
> > 1. Extensive use of list comprehensions
> > 2. Lazy lists
> > 
> > Just change in the above 'list' to 'generator'
> > and more or less it should work in python
> > 
> > More or less that means when you have a comprehension
> > [expr for x in list2 for y in list2 etc]
> > 
> > change the '[]' to '()'
> > and recursively change the list1 list2 to gen1 gen2
> > 
> > Some nuisances that bug me (or I dont know how to handle):
> > 
> > 1. Singleton
> >    [val] becomes (x for x in [val])  (Hoo Boy!)
> > 
> >    Or 
> >    def single_val(): yield val
> 
> It's just one def:
> 
> def sing(*args):
>    for arg in args:
>        yield arg
> 
> Or not even that: iter((val,)).


Sweet


> 
> But see below at the end.
> 
> > 2. Nice syntax like list +
> > 
> > Compare [1] + [2]
> > with
> > 
> > >>> from itertools import chain
> > >>> a = (x for x in [1])
> > >>> b = (x for x in [2])
> > >>> list(chain(a,b))
> > [1, 2]
> > 
> > Of course it looks worse because the (syntax) overhead of jumping
> > between lists and generators overwhelms in this trivial case
> 
> Yes, one wouldn't jump back and forth so much. Just collect the result
> at the end.
> 
> >>> list(chain(sing(3,1,4), sing(1), sing(5,9,2,6)))
> [3, 1, 4, 1, 5, 9, 2, 6]
> 
> >>> list(chain(sing(3,1,4,1), sing(), sing(5,9,2,6)))
> [3, 1, 4, 1, 5, 9, 2, 6]
> 
> And it gets better: chain takes lists! And tuples! For those who like
> their brackets round:
> 
> >>> tuple(chain((3,1,4,1), (), (5,9,2,6)))
> (3, 1, 4, 1, 5, 9, 2, 6)
> 
> >>> set(chain((3,)))
> {3}
> 
> >>> list(chain(()))
> []
> 
> So chain does it all.

Neat 
Thanks

[toc] | [prev] | [next] | [standalone]

#84582

Johannes Bauer <dfnsonfsduifb@gmx.de> writes:

> So, I would like to ask if you have a Pythonic approach to
> backtracking problems? If so, I'd love to hear your solutions!

I'm not aware of what the problem is. “Back-tracking” doesn't have a
general meaning I recognise beyond random access into a data structure.
So a Python list is the obvious starting point.

Do you have a specific meaning of “back-tracking” that implies
particular problems that are difficult to solve?

-- 
 \       “The Vatican is not a state.… a state must have people. There |
  `\    are no Vaticanians.… No-one gets born in the Vatican except by |
_o__)        an unfortunate accident.” —Geoffrey Robertson, 2010-09-18 |
Ben Finney

[toc] | [prev] | [next] | [standalone]

#84585

Ben Finney <ben+python@benfinney.id.au>:

> “Back-tracking” doesn't have a general meaning I recognise beyond
> random access into a data structure.

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.


Marko

[toc] | [prev] | [next] | [standalone]

#84586

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.

ChrisA

[toc] | [prev] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#85181

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

[toc] | [prev] | [next] | [standalone]

#84583

On 2015-01-26 00:32, Ben Finney wrote:
> Johannes Bauer <dfnsonfsduifb@gmx.de> writes:
>
>> So, I would like to ask if you have a Pythonic approach to
>> backtracking problems? If so, I'd love to hear your solutions!
>
> I'm not aware of what the problem is. “Back-tracking” doesn't have a
> general meaning I recognise beyond random access into a data structure.
> So a Python list is the obvious starting point.
>
> Do you have a specific meaning of “back-tracking” that implies
> particular problems that are difficult to solve?
>
I believe he's talking about trying different alternatives until one
works. You get it in matching regexes (well, when using the NFA
approach as used in the re module, Perl regexes, etc, anyway).

[toc] | [prev] | [next] | [standalone]

#84593

On 26/01/2015 00:32, Ben Finney wrote:
> Johannes Bauer <dfnsonfsduifb@gmx.de> writes:
>
>> So, I would like to ask if you have a Pythonic approach to
>> backtracking problems? If so, I'd love to hear your solutions!
>
> I'm not aware of what the problem is. “Back-tracking” doesn't have a
> general meaning I recognise beyond random access into a data structure.
> So a Python list is the obvious starting point.
>
> Do you have a specific meaning of “back-tracking” that implies
> particular problems that are difficult to solve?
>

As good a definition here http://en.wikipedia.org/wiki/Backtracking as 
any.  As elsewhere in this thread it mentions sudoku.  To me this 
http://norvig.com/sudoku.html is a classic example of putting theory 
into practice.  Read and weep :)

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#84641

On Sunday, January 25, 2015 at 4:15:58 PM UTC-4, Johannes Bauer wrote:
> Hi folks,
> 
> I have a problem at hand that needs code for backtracking as a solution.
> And I have no problem coding it, but I can't get rid of the feeling that
> I'm always solving backtracking problems in a non-Pythonic
> (non-idiomatic) way. So, I would like to ask if you have a Pythonic
> approach to backtracking problems? If so, I'd love to hear your solutions!

When I think of backtracking, I think of Prolog (to which backtracking is central).  You could use PySWIP to run SWI-Prolog from your Python program.  Not idiomatic Python backtracking, of course, but it would get the job done, and Prolog's backtracking is reliable and well-described.  It would help if you already know a bit of Prolog or are keen to learn.

Cheers,
  Steve J. Martin

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web