N-Queens

Place n queens on an n by n board so that no two attack each other (same row, column, or diagonal).

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

def solve_n_queens(n):
    cols = []                                  # cols[r] = column of the queen in row r
    def safe(r, c):
        return all(c != c2 and abs(c - c2) != r - r2 for r2, c2 in enumerate(cols))
    def dfs(r):
        if r == n: return True
        for c in range(n):
            if safe(r, c):
                cols.append(c)
                if dfs(r + 1): return True
                cols.pop()                     # backtrack
        return False
    return cols if dfs(0) else None