バックトラッキング

backtracking.py

def permutations(items):
    result, path = [], []
    used = [False] * len(items)

    def backtrack():
        if len(path) == len(items):
            result.append(path[:])      # store a copy of the full path
            return
        for i, x in enumerate(items):
            if used[i]:
                continue
            used[i] = True              # choose
            path.append(x)
            backtrack()                 # explore
            path.pop()                  # unchoose
            used[i] = False

    backtrack()
    return result


def n_queens(n):
    cols, diag, anti = set(), set(), set()

    def place(row):
        if row == n:
            return 1
        count = 0
        for c in range(n):
            if c in cols or row - c in diag or row + c in anti:
                continue                # prune: square is attacked
            cols.add(c); diag.add(row - c); anti.add(row + c)
            count += place(row + 1)
            cols.remove(c); diag.remove(row - c); anti.remove(row + c)
        return count

    return place(0)


print(permutations([1, 2, 3]))
print(n_queens(8))  # 92

python backtracking.py