Lesson 5

The idea we will use is known as backtracking: we will build the permutation step by step, and if the beginning of the permutation already contains a conflict (i.e., queens attacking each other), then we will not attempt to continue that branch.

from functools import partial


def solutions(n):
    def is_valid_extension(permutation, next_j):
        next_i = len(permutation)
        return next_j not in permutation and all(next_i - i != abs(next_j - j) for i, j in enumerate(permutation))

    def helper(permutation):
        if len(permutation) == n:
            yield permutation
        else:
            validator = partial(is_valid_extension, permutation)
            for next_j in filter(validator, range(n)):
                yield from helper(permutation + [next_j])

    return helper([])


print(next(solutions(15)))

[0, 2, 4, 1, 9, 11, 13, 3, 12, 8, 5, 14, 6, 10, 7]

The corresponding trees for \(n=3\) and \(n=4\) are shown below. Note that there are fewer leaves in them than in full trees (whose leaves contain all permutations).