# LeetCode N-Queens I and II: Backtracking and DFS

## Overview

LeetCode N-Queens I and II are the classic backtracking problems which could be solved by using DFS + Pruning to enumerate all the solutions.

## LeetCode N-Queens I and II

The *n*-queens puzzle is the problem of placing *n* queens on an *n* * *n* chessboard such that no two queens attack each other.

Given an integer *n*, return all distinct solutions to the *n*-queens puzzle.

Each solution contains a distinct board configuration of the *n*-queens’ placement, where `'Q'`

and `'.'`

both indicate a queen and an empty space respectively.

For example,

There exist two distinct solutions to the 4-queens puzzle:

[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]

(2)

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

## Analysis: Backtracking and DFS

Both could be solved by backtracking algorithm with pruning. When generating candidates, remove all the positions which obviously lead to conflicts (Queens attack). After all the n queens are placed, the final configuration is stored for I and the global count increases by 1 for II. The following code enumerates all the valid solutions for the N-Queens problem and could be adjusted a bit to solve the second one and it is accepted by LeetCode OJ to pass both N-Queens problems:

class Solution { public: vector<vector<string>> results; vector<string> board; vector<int> cols; void dfs(int k, int n) { if (k == n) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { board[i][j] = '.'; if (cols[i] == j) board[i][j] = 'Q'; } } results.push_back(board); return ; } for (int j = 0; j < n; ++j) { bool cand = true; for (int i = 0; cand && i < k; ++i) { if (cols[i] == j || abs(k - i) == abs(cols[i] - j)) { cand = false; } } if (cand) { cols[k] = j; dfs(k + 1, n); } } } vector<vector<string> > solveNQueens(int n) { results.clear(); if (n == 1) { vector<string> vec; vec.push_back("Q"); results.push_back(vec); return results; } if (n <= 3) return results; cols.resize(n); fill(cols.begin(), cols.end(), -1); board.resize(n); for (int i = 0; i < n; ++i) board[i].resize(n); dfs(0, n); return results; } };

**Remarks:**

- For II, one might still save some time computation by the symmetric property. And for this classical N-Queens problem, n can’t be too large, when n = 14, it might take several minutes to solve.
- What about iterative implementation? Is it easier? You might also want to search the bit mask solution for any further reference

## Summary

LeetCode N-Queens I and II are the classic backtracking problems which could be solved by using DFS + Pruning to enumerate all the solutions.