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 the number of distinct solutions to the n-queens puzzle.
Example:
Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
1 class Solution { 2 public: 3 bool valid(vector<int>&a, int x, int y) { 4 for (int i = 0; i < x; i++) 5 if (y == a[i] || abs(a[i] - y) == x - i) 6 return false; 7 return true; 8 } 9 void build(int&ans,vector<int>&now,int row) { 10 int n = now.size(); 11 if (row == n) 12 ans++; 13 else { 14 for (int i = 0; i < n; i++) 15 if (valid(now, row, i)) { 16 now[row] = i; 17 build(ans, now, row + 1); 18 } 19 } 20 } 21 int totalNQueens(int n) { 22 vector<int>now(n, -1); 23 int ans = 0; 24 build(ans, now, 0); 25 return ans; 26 } 27 };
用&传送参数可以快好多，终于知道上一题为什么比别人慢了
19.2.8 [LeetCode 51] N-Queens II
原文：https://www.cnblogs.com/yalphait/p/10356335.html
