[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

Follow up for N-Queens problem.

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

思路：

经典8皇后问题的推广版n皇后问题。两题其实是一回事，I的难度反而更大一些。因为能解I得到所有解，必然能知道一共几个解从而能解II。同样也是类似DFS的backtracking问题。难点在于如何判断当前某一位置是否可以放皇后，需要通过之前所有放置过的皇后位置来判断。对已经放置的任意皇后，需要判断当前位置是否在同一行、列、对角线上这三个条件。

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<vector<string> > solveNQueens(int n) { vector<vector<string>> allSol; vector<string> sol; vector<int> col; solveNQ(n, 0, col, sol, allSol); return allSol; } void solveNQ(int n, int irow, vector<int> &col, vector<string> &sol, vector<vector<string>> &allSol) { if(irow==n) { allSol.push_back(sol); return; } for(int icol=0; icol<n; icol++) { if(validPos(col, irow, icol)) { string s(n,'.'); s[icol] = 'Q'; sol.push_back(s); col.push_back(icol); solveNQ(n, irow+1, col, sol, allSol); sol.pop_back(); col.pop_back(); } } } bool validPos(vector<int> &col, int irow, int icol) { if(irow<col.size()) return false; for(int i=0; i<col.size(); i++) { if(icol==col[i] || abs(irow-i)==abs(icol-col[i])) return false; } return true; } };

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<int> col; int totSol = 0; solveNQ(n, 0, col, totSol); return totSol; } void solveNQ(int n, int irow, vector<int> &col, int &totSol) { if(irow==n) { totSol++; return; } for(int icol=0; icol<n; icol++) { if(validPos(col, irow, icol)) { col.push_back(icol); solveNQ(n, irow+1, col, totSol); col.pop_back(); } } } bool validPos(vector<int> &col, int irow, int icol) { if(irow<col.size()) return false; for(int i=0; i<col.size(); i++) { if(icol==col[i] || abs(irow-i)==abs(icol-col[i])) return false; } return true; } };