Idiomatic backtracking in Python

[Ian Foote]

-----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-----