Idiomatic backtracking in Python
rustompmody at gmail.com
Mon Jan 26 03:41:31 CET 2015
On Monday, January 26, 2015 at 2:21:34 AM UTC+5:30, Ian Foote wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 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):
> if matches_condition(data):
> yield data
> 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.
> 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"
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):
[val] becomes (x for x in [val]) (Hoo Boy!)
def single_val(): yield val
2. Nice syntax like list +
Compare  + 
>>> from itertools import chain
>>> a = (x for x in )
>>> b = (x for x in )
Of course it looks worse because the (syntax) overhead of
jumping between lists and generators overwhelms in this trivial case
More information about the Python-list