# 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)

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:

Remarks:

1. 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.
2. 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.

Written on May 26, 2013