Idiomatic backtracking in Python

[Rustom Mody]

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