## Tuesday, November 18, 2014

### [LeetCode] N-Queens I, II

N-Queens I

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

N-Queens II

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

1. 逐行放置皇后：排除在同一行的可能。
2. 记录之前所放皇后的列坐标：col[i]=j表示第i行的皇后在第j列。这样在放置第i+1行时，只要保证col[i+1] != col[k], k=0...i 即可。
3. 对角线判断：对于任意(i1, col[i1])和(i2, col[i2])，只有当abs(i1-i2) = abs(col[i1]-col[i2])时，两皇后才在同一对角线。

N-Queens I

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38``` ```class Solution { public: vector > solveNQueens(int n) { vector> allSol; vector sol; vector col; solveNQ(n, 0, col, sol, allSol); return allSol; } void solveNQ(int n, int irow, vector &col, vector &sol, vector> &allSol) { if(irow==n) { allSol.push_back(sol); return; } for(int icol=0; icol &col, int irow, int icol) { if(irow

N-Queens II

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33``` ```class Solution { public: int totalNQueens(int n) { vector col; int totSol = 0; solveNQ(n, 0, col, totSol); return totSol; } void solveNQ(int n, int irow, vector &col, int &totSol) { if(irow==n) { totSol++; return; } for(int icol=0; icol &col, int irow, int icol) { if(irow