N-Queens (count solutions)

Given a board size n, print how many distinct ways n queens can be placed on an n x n chessboard so that no two queens attack each other (same row, column, or diagonal).

Example

Input: 4 Output: 2

Approach

Place queens one row at a time. At each row, try every column; a column is safe if it's not already used, and neither diagonal (row - col and row + col — each diagonal shares one of these two values for every cell on it) is already occupied. Track used columns/diagonals in sets for O(1) safety checks, place, recurse to the next row, then remove before trying the next column.

Input format

Line 1: n

Print the number of distinct valid placements.