Backtracing without Recusion in Python
Posted on Thu, 03 Nov 2016 in Python
As you know there is no tail recursion optimization in Python. Moreover it has a very low recursion limit. It can be a problem if you are trying to solve the problem using the backtracking algorithm. Recursion limit is big enough to solve sudoku, but an exception will raise if the problem has more possible solutions.
However implementation of backtracking in Python with recursion is elegant. It's easy to read and understand.
def backtrack(self, solution):
if solution in self.seen_solutions:
return
if self.reject(solution):
return
if self.accept(solution):
self.output(solution)
for child_solution in self.child_solutions(solution):
self.backtrack(child_solution)
When you rich recursion limit, you can switch to this template without recursion. It doesn't look so clean as one with recursion, but it's not so ugly than it could be, and it uses the same auxiliary functions.
def backtrack(self, solution):
solution_stack = [self.child_solutions(solution)]
while True:
current_generator = solution_stack[-1]
solution = next(current_generator, None)
while solution:
if self.reject(solution):
solution = next(current_generator, None)
continue
if self.accept(solution):
self.output(solution)
if not self.solution_is_complete(solution):
solution_stack.append(self.child_solutions(solution))
current_generator = solution_stack[-1]
solution = next(current_generator, None)
solution_stack = solution_stack[:-1]
if not solution_stack:
return
---
Got a question? Hit me on Twitter: avkorablev
Got a question? Hit me on Twitter: avkorablev