Path: csiph.com!usenet.pasdenom.info!news.etla.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Sun, 25 Jan 2015 20:51:03 +0000
From: Ian Foote <ian@feete.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.3.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Idiomatic backtracking in Python
References: <ma3itj$ol6$1@news.albasani.net>
In-Reply-To: <ma3itj$ol6$1@news.albasani.net>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.18134.1422219082.18130.python-list@python.org>
Lines: 69
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python: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=3DNone):
    if data is None:
        yield from backtrack_solver(data=3Dinitial_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,
>=20
> 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!
>=20
> Cheers, Johannes
>=20

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQEcBAEBAgAGBQJUxVc3AAoJEODsV4MF7PWzO+sH/jaz0Dc7Hs9LkbB8g6//A7pK
bxBeFSVtmvaHynASg2PRAzSAC4dty5R52myPoXB3Hdf+otTjBUjOyA7k5j+HCDum
TeJJSUFwOFQxr3yRtXcYoct+xYGBAGRqjT0oiGJMFYp5dLPXmHsAv10KIr3HcOo4
TgqQ9XtyMw60Tmx1ZJ/pj0xOPtrr5PUxe0bwRC5bRycDS943s+UJ/o42DhnBtkZp
h6kkqsZsAL27i0hZrqBEfWMaIHbY9DZNzA9PYyYEl/pzvtB0tpN6ENrxTQFbBNeE
SZoEz9AdcUr9D0ej3HaTgmbT/ivl0op4xQdnpp75uRnGpaH5LlssEGbWQsmRwsY=3D
=3DJpwv
-----END PGP SIGNATURE-----