Backtracking with Pruning

What is pruning?

If you look up "pruning" on Google Images, this is what you get:

It literally means cutting branches off a tree.

In our case, we want to cut branches off our state-space tree. The fewer branches, the faster the algorithm runs.

When do we want to prune a branch?

When it's clear that going into that branch would not yield a valid final state. This happens when the problem comes with one or more constraints, and the branches violates those contraints.

Template v1.1

Here we introduce an updated template.

1function dfs(start_index, path):
2if is_leaf(start_index):
3   report(path)
4   return
5for edge in get_edges(start_index):
6  # prune if needed
7  if not is_valid(edge):
8    continue
9  path.add(edge)
10  # increment start_index
11  dfs(start_index + len(edge), path)
12  path.pop()

The differences are

• we added a pruning step that checks if a branch is valid using is_valid
• we increment start_index by a variable size instead of always 1