# Title: N-Queens
# Heading: Python Program to Solve the N-Queens Problem
# Level: advanced
# Tags: n queens, eight queens, backtracking, chessboard, recursion
# Time: O(n!)
# Space: O(n)
# About: Places N queens on an N×N chessboard so that no two attack each other, trying each column row by row and backing up from dead ends.

def is_safe(queens, row, col):
    """True if no queen in queens attacks the square (row, col)."""
    for r, c in enumerate(queens):
        # Same column, or on a diagonal: as far across as down
        if c == col or abs(c - col) == row - r:
            return False
    return True


def n_queens(n):
    """Every safe placement of n queens, as lists of columns."""
    solutions = []
    queens = []  # queens[r] is the column of the queen in row r

    def place(row):
        if row == n:
            solutions.append(queens.copy())
            return
        for col in range(n):
            if is_safe(queens, row, col):
                queens.append(col)  # choose this square
                place(row + 1)      # fill the rows below
                queens.pop()        # undo, to try the next column

    place(0)
    return solutions


size = 4
solutions = n_queens(size)
print(f"{len(solutions)} solutions for {size} queens. The first:")
for col in solutions[0]:
    print(" ".join("Q" if c == col else "." for c in range(size)))