Count N-Queens Solutions
Hard · Recursion
Place n chess queens on an n x n board so that no two attack each other: no shared row, column or diagonal. Backtracking places one queen per row and only tries columns that are still safe.
To check safety in O(1), keep three sets: used columns, used "down" diagonals (row - col is the same along one) and used "up" diagonals (row + col is the same along one). Add to the sets before recursing and remove after (undo the choice).
Write count_queens(n) that returns how many different solutions exist. 1 <= n <= 9.