N-Queens

Place N queens so none share a row, column, or diagonal. Place row by row; the moment a row has no safe square, undo the previous row's choice — pruning entire subtrees at once.

Category

Backtracking

Time complexity

O(n!)

Space complexity

O(n)

Pseudocode

try each column in this row
safe → place, go to next row
attacked → try next column
no column works → backtrack
all rows placed → solution

Reference implementation

def place(row):
    for col in range(n):
        if safe(row, col):
            queens.append(col)
            if place(row + 1): return True
            queens.pop()  # backtrack

Open the interactive N-Queens visualisation →