# N-Queens Problem: Backtracking Implementation in C++ (Full Explanation) ## Introduction The N-Queens problem asks: how can N queens be placed on an N×N chessboard so that no two queens threaten each other? This classic backtracking problem demonstrates recursion, pruning, and search-state reasoning. This post explains a standard recursive solution as implemented in the repository, shows how the place function enforces constraints, lists complexity considerations, and provides sample outputs. --- ## Approach summary We place queens row by row. For each row k, we try columns 1..N. Before placing a queen at column i, we check whether any earlier queen conflicts in the same column or either diagonal. If place(k,i) returns true, we put the queen and recurse to the next row. If we reach row N, we print a valid solution. This is a textbook depth-first backtracking solution. --- ## Repository implementation (reference) Source: https://github.com/mashrur-rahman-fahim/algorithm/blob/main/nQueens.cpp. Key parts of the implementation: - place(k, i, sol) checks two constraints: - column conflict: sol[j] == i for some earlier row j - diagonal conflict: abs(sol[j] - i) == abs(j - k) (same diagonal condition) - nQueens(sol, k, n) iterates possible column placements for row k, sets sol[k] = i, and recurses. - The code prints each complete solution as a sequence of sol[1] .. sol[n] (1-based column indices for each row). --- ## Example: n = 4 (common small test) For n = 4 there are 2 distinct solutions. The implementations typically produce these placements (row → column): - 2 4 1 3 - 3 1 4 2 If you run the code and enter 4, you should see two lines containing the column indices for each valid board arrangement. --- ## Correctness & pruning - The place test is sufficient to ensure no queen can attack another because: - Column check avoids vertical attacks. - abs diagonal check avoids both \ and // diagonals. - Additional pruning (bitmask-based) can be used for speed when N is large; the presented algorithm works fine up to moderate N (N ~ 12–15) in reasonable time. --- ## Complexity - The exact complexity is exponential. Backtracking explores a search tree with branching factor up to N and depth N, so worst-case complexity is O(N!) in the naive sense. In practice, pruning reduces the explored nodes considerably. --- ## Improvements & variants 1. Bitmask optimization — use three bitmasks to represent occupied columns and diagonals; this significantly speeds the search and reduces memory. 2. Symmetry breaking — for counting solutions only, exploit board symmetry to halve work for even/odd N. 3. Parallelization — solve different first-row choices on different threads. --- Repository: https://github.com/mashrur-rahman-fahim/algorithm/blob/main/nQueens.cpp Images (use in article): 1. https://www.shutterstock.com/image-photo/programmer-cyber-security-technology-male-600nw-2464110045.jpg 2. https://www.snexplores.org/wp-content/uploads/2020/11/1030_algorithm_explainer-1028x579.jpg 3. https://i0.wp.com/bdtechtalks.com/wp-content/uploads/2022/02/algorithm-formulation.jpg?ssl=1