Trying everything, but not stupidly

Some problems have no clever rule. Place eight queens on a chessboard so none attack each other. Fill a Sudoku grid. Find every permutation.

For these the answer is to search, and the skill is in abandoning bad branches early.

The shape

def solve(state):
    if is_complete(state):
        record(state)
        return
    for choice in options(state):
        if not valid(state, choice):
            continue          # prune: do not explore this at all
        apply(state, choice)
        solve(state)
        undo(state, choice)   # backtrack

The undo is what makes it backtracking rather than plain recursion. One state is mutated on the way down and restored on the way up, instead of copying it at every level.

Permutations

def permutations(nums):
    result, used, current = [], [False] * len(nums), []

    def walk():
        if len(current) == len(nums):
            result.append(current[:])      # copy, or every entry aliases
            return
        for i, n in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            current.append(n)
            walk()
            current.pop()                  # undo
            used[i] = False                # undo
    walk()
    return result

The current[:] is the bug people hit: appending the list itself stores a reference to something that keeps changing, and every result ends up empty.

Pruning is the entire point

Eight queens has 64 choose 8, around 4.4 billion placements. Checking each is hopeless.

Placing one queen per row cuts it to 8 to the power 8, about 16 million. Rejecting a column or diagonal already attacked, as soon as it is placed rather than at the end, cuts it to roughly 2,000 positions explored.

The same code with and without that one check is the difference between instant and never finishing.

Telling it apart from dynamic programming

Both explore choices. They differ in what they produce:

• Backtracking enumerates actual solutions: the arrangements, the paths, the valid grids. It cannot memoise, because each answer is a distinct object.
• Dynamic programming computes a value, a count or a best, and reuses overlapping subproblems.

"List every valid arrangement" is backtracking. "How many arrangements are there" is often dynamic programming.