292. Print All N-Queens Solutions

Given an integer n, find every distinct way to place n queens on an n x n chessboard such that no two queens attack each other (no two share a row, column, or diagonal). Represent each solution as the column positions (1-indexed) of the queen in row 1, row 2, ..., row n, in that order. Print every solution on its own line as space-separated column positions, with solutions ordered by that sequence (compare left to right, smaller first). If no solution exists, print 'NONE'.

Input: A single line containing the integer n. Output: Print every solution on its own line as n space-separated 1-indexed column positions, ordered lexicographically; print 'NONE' if no solution exists.

1 <= n <= 9

Trying columns in ASCENDING order at every row (rather than some other order) is precisely what guarantees the printed solutions come out in the sorted order the problem requires - no separate sorting step needed afterward.

Print every distinct way to place n queens on an n x n chessboard so that none attack each other. Brute force: Generate every possible placement of n queens (choosing n cells from n²) and filter for valid non-attacking arrangements afterward - hugely wasteful compared to only ever exploring placements that remain valid at every step. Optimised: The same 'one queen per row, prune attacked columns/diagonals immediately' technique used for counting N-Queens solutions applies directly here - the only difference is RECORDING the actual column sequence when a full valid placement is found, instead of just incrementing a counter.

Place queens one row at a time via backtracking: before placing a queen in a given column of the current row, check in O(1) whether that column, or either diagonal through this cell, is already occupied by a previously placed queen, using three boolean/bitmask sets (columns, and the two diagonal directions indexed by row-col and row+col). If a conflict is found, skip that column immediately rather than continuing to build an already-invalid arrangement; only recurse into the next row when the placement is currently safe. This prunes huge parts of the search tree as early as possible - the moment a conflict is introduced - rather than only detecting invalidity after a full permutation is built, which is what makes it dramatically faster in practice than the permutation approach despite having the same worst-case bound. Time: O(n!) worst case, much smaller in practice due to pruning Space: O(n)

Since no two queens may share a column, restrict the search to genuine permutations of columns across the n rows (i.e., each column used exactly once) instead of arbitrary assignments - this alone rules out all row/column conflicts by construction. Generate all n! such permutations and, for each complete one, check only for diagonal conflicts (row difference equals column difference) at the end. This shrinks the search space from n^n down to n!, a major improvement, though it still wastes work building and fully checking permutations that violate a diagonal constraint early on. Time: O(n! * n) Space: O(n)

Generate every possible placement of n queens, one per row, allowing any column (including repeats across rows) - that is, all n^n row-to-column assignments - and for each complete assignment, check from scratch whether any two queens share a column or a diagonal. Keep only the assignments that pass the check. This is correct because it considers literally every conceivable arrangement, but the search space is enormous and almost all placements are invalid before even finishing. Time: O(n^n * n^2) Space: O(n)

1. Place queens one row at a time, trying columns in ASCENDING order and skipping any attacked by a previously placed queen. 2. Trying columns in ascending order at every row is exactly what naturally produces solutions already in the required sorted order. 3. When all n rows are successfully filled, record the column positions as one complete solution; backtrack (unplace the queen) after fully exploring each branch.

Time: O(n!) in the worst case for the search itself, plus O(n) per solution found to record it. Space: O(n) for the recursion/tracking sets, plus O(number of solutions * n) for storing all found solutions.

Test n = 2 or n = 3 (no solution, print 'NONE'), n = 1 (single trivial solution), and n = 9 (largest case for performance).

Be ready to connect this directly to the 'count N-Queens solutions' problem - recognizing that printing versus counting requires only a trivial change (record instead of increment) to the exact same backtracking search is a strong signal.