题目：
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
Show Tags
Show Similar Problems
链接： http://leetcode.com/problems/n-queens-ii/
题解：
刚昨晚NQueens I， 这换个问题又算一题...不过省了我们很多事。只需要设一个global的count来记录找到解的数目。
Time Complexity - O(nn), Space Complexity - O(n)
public class Solution {
private int count = 0;
public int totalNQueens(int n) {
if(n <= 0)
return count;
int[] queens = new int[n]; // queens must be a permutation of n
trySolveNQueens(queens, 0);
return count;
}
private void trySolveNQueens(int[] queens, int pos) {
int len = queens.length;
if(pos == len)
count++;
else {
for(int i = 0; i < len; i++) {
queens[pos] = i;
if(isBoardValid(queens, pos))
trySolveNQueens(queens, pos + 1);
}
}
}
private boolean isBoardValid(int[] queens, int pos) {
for(int i = 0; i < pos; i++) {
if(queens[i] == queens[pos]) // column conflicts
return false;
else if(Math.abs(queens[pos] - queens[i]) == Math.abs(i - pos)) // diagonal conflicts
return false;
}
return true;
}
}
二刷：
Java:
上一题的简化版本，只需要求有多少种solution就可以了。以后再了解一下NQueens的fancy做法
Time Complexity - O(nn), Space Complexity - O(n)
public class Solution {
private int totalQueens = 0;
public int totalNQueens(int n) {
if (n <= 0) {
return 0;
}
int[] queens = new int[n];
trySolveNQueens(queens, 0);
return totalQueens;
}
private void trySolveNQueens(int[] queens, int pos) {
if (pos == queens.length) {
totalQueens++;
} else {
for (int i = 0; i < queens.length; i++) {
queens[pos] = i;
if (isBoardValid(queens, pos)) {
trySolveNQueens(queens, pos + 1);
}
}
}
}
private boolean isBoardValid(int[] queens, int pos) {
for (int i = 0; i < pos; i++) {
if (queens[i] == queens[pos]) {
return false;
}
if (Math.abs(queens[i] - queens[pos]) == Math.abs(i - pos)) {
return false;
}
}
return true;
}
}
Reference: