N-Queens

medium ~35 min

Place n queens on an n x n chessboard so that no two share a row, a column or a diagonal. Write solve_n_queens(n) that returns every such placement.

1 <= n <= 10.
Each placement is a list of n strings of length n: row r has 'Q' in the queen's column and '.' everywhere else.
The placements may come in any order.

Generating all n! column orders and filtering them afterwards is too slow for n = 10: the tests allow 1.5 seconds.

solve_n_queens(4)
# [[".Q..",
#   "...Q",
#   "Q...",
#   "..Q."],
#  ["..Q.",
#   "Q...",
#   "...Q",
#   ".Q.."]]
solve_n_queens(2)   # []

Show hint

every row holds exactly one queen, so place them row by row and abandon a partial board as soon as a queen is attacked. Cells on the same diagonal share r - c, and on the same anti-diagonal r + c, which makes each safety check O(1).

Topic: Recursion and backtracking. Choose, recurse, un-choose: subsets, permutations, N-queens, pruning.

Read the visual guide