What is the time complexity of n-queens?

Worst case O(n!). Space complexity is O(n). One queen per row cuts the space to nⁿ before pruning; pruning does the rest.

N-Queens

hard

Diagonals are just r−c and r+c, so the safety test is three hash lookups. Rejecting a placement at row 2 kills every branch beneath it - which is where all the performance lives.

Worst O(n!)Space O(n)

Loading the n-queens engine…

Where to go next

Sudoku solver

hard

Try, recurse, undo - plus one ordering trick.

Permutations

medium

Swap in place, recurse, swap back.

Rat in a maze

medium

Watch corridors light up and go dark again.