N-Queens Count

Given an integer N, count the number of distinct ways to place N queens on an N×N chessboard such that no two queens attack each other - that is, no two queens share a row, a column, or a diagonal. Solve this using backtracking recursion that places one queen per row and prunes any branch where a queen would attack a previously placed queen.

Input: A single line containing the integer N. Output: A single line containing the total number of valid placements of N non-attacking queens on the N×N board.

1 <= N <= 10.

This is the quintessential BACKTRACKING problem - placing one queen per row, checking validity immediately, and backtracking on conflict (rather than checking only after a FULL arrangement is built) is what makes the search tractable at all for even moderately sized N.

Count how many ways N queens can be placed on an N×N chessboard so that none attack each other. Brute force: Try every possible way to place N queens anywhere on the board (not restricted to one per row) and check each full arrangement for conflicts - this is combinatorially enormous, since there are C(N², N) ways to just choose the squares, before even checking validity. Optimised: Restricting the search to EXACTLY one queen per row (since no two queens can ever share a row anyway) immediately eliminates a huge class of invalid arrangements from ever being considered, and checking each candidate placement against already-placed queens' columns and diagonals in O(1) (via tracked sets) lets the search PRUNE invalid branches immediately, rather than only detecting conflicts after a full arrangement is built.

1. Place queens ONE PER ROW, working row by row. 2. For each row, try every column, and recurse into the NEXT row only if the placement doesn't conflict with any queen already placed (checking columns and both diagonal directions). 3. The BASE CASE is placing a queen successfully in EVERY row (row == N) - that's one complete, valid configuration; increment the count and backtrack to look for more.

Time: O(N!) in the worst case (an exponential search bounded loosely by permutations of column choices), though pruning makes it run much faster in practice for the given small N (up to 10). Space: O(N), for tracking occupied columns and diagonals, plus O(N) recursion stack depth.

N = 1 has exactly 1 valid placement. N = 2 and N = 3 have 0 valid placements - it is impossible to place that many non-attacking queens on boards that small. N = 10 is the largest input this problem is tested with.

Be ready to explain how tracking 'row - col' and 'row + col' as constant values along each diagonal direction lets diagonal conflicts be checked in O(1), rather than re-scanning the board - a key efficiency detail in any N-Queens implementation.