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

Groups > comp.lang.python > #84580

Re: Idiomatic backtracking in Python

Show key headers only | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web