N-Queens

The N-Queens puzzle asks you to place N chess queens on an N×N board so that no two of them attack each other. A queen attacks along its entire row, its entire column, and both diagonals, so a placement is valid only when every pair of queens differs in row, in column, and in diagonal. This is the classic backtracking interview problem — LeetCode 51 (return every board) and 52 (just count them) — a size-N generalization of the eight queens puzzle. You will return both every distinct placement and, separately, how many there are, packaged on one object nQueens = { solve, count }.

Signature

nQueens.solve(n)   // integer n -> array of every distinct solution
nQueens.count(n)   // integer n -> number of distinct solutions

Each solution is an array cols of length n where cols[row] is the 0-based column of the queen in that row. Because there is exactly one queen per row, a single number pins each queen's position. count(n) always equals solve(n).length.

Examples

nQueens.solve(4);
// [[1, 3, 0, 2], [2, 0, 3, 1]]   (the two 4x4 boards; order not significant)
// [1, 3, 0, 2] reads: row 0 -> col 1, row 1 -> col 3, row 2 -> col 0, row 3 -> col 2

nQueens.count(8);   // 92  — the eight-queens board has 92 distinct solutions

nQueens.solve(2);   // []  — no way to place 2 queens on a 2x2 board without conflict
nQueens.solve(3);   // []  — 3x3 has no solution either

Notes

• One queen per row — a valid board has exactly one queen in each row (n queens on n rows means no row can hold two or sit empty), so it is enough to choose a column for each row. Assume this representation; you never place two queens in one row.
• The cols shape — return cols[row] = column, not a grid of strings or [row, col] pairs. For n = 4, [1, 3, 0, 2] and [2, 0, 3, 1] are the two solutions.
• Order does not matter — solve may return the solutions in any order; they are compared as a set.
• Small n only — the number of solutions has no closed form and grows fast (1, 0, 0, 2, 10, 4, 40, 92 for n = 1..8), so tests stay at n ≤ 8.
• Guard n < 1 — treat any n below 1 as zero solutions: solve returns [] and count returns 0.