N-Queens Count

Problem

Count the number of ways to place n non-attacking queens on an n by n chessboard.

Backtrack row by row, tracking occupied columns and both diagonal families in sets, and prune any square attacked by an earlier queen. By convention n = 0 counts as one empty placement, and n_queens(8) equals 92.

Hint

A queen at (r, c) attacks row r, column c, diagonal r - c and anti-diagonal r + c.

Test cases

case 1

in: [0]

expected: 1

case 2

in: [1]

expected: 1

case 3

in: [4]

expected: 2

case 4

in: [6]

expected: 4

case 5

in: [8]

expected: 92

Starter codePython

def n_queens(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor