N Queens I@leetcode

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.."]
]

This is a typical backtracking problem. We have to traverse all the possible cases of solution space, then to see whether it fits the judging condition or lot. We can compare this problem to permutations, Combinations, Combination Sum, Soduku solutions, Palindrome partitions, word break II. They can all classify to same pattern. The time complexity is O(N^N).

Steps,
1. Open solution space. vector<string > tmp(n, string(n, ' . ')), vector<vector<string> > res.
tmp is used to hold temporary solution, once it meets the condition, it should be pushed into result.

2. Define conditions and write a separate function to judge if the condition is complex. In here, we traverse the board row by row, then we need to see in each row, every columns and diagonal lines have 'Q' or not. Pay attention here is that there are two diagonal lines.

3. Write backtracking pattern. Once row == tmp.size() -> res.push_back(tmp). else, traverse each row, for each row, check each columns and diagonal lines, fill in Queens if allowed.

 Iterative method is kind of hard. 

N Queens II