Idiomatic backtracking in Python
ian at feete.org
Sun Jan 25 21:51:03 CET 2015
-----BEGIN PGP SIGNED MESSAGE-----
I think a very idiomatic way to implement backtracking is using a
recursive generator (python 3):
if data is None:
yield from backtrack_solver(data=initial_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
`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.
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
-----END PGP SIGNATURE-----
More information about the Python-list