题目：

Follow up for N-Queens problem.

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

 

Show Tags

Show Similar Problems

 

链接： 

题解：

刚昨晚NQueens I， 这换个问题又算一题...不过省了我们很多事。只需要设一个global的count来记录找到解的数目。

Time Complexity - O(nⁿ), 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(nⁿ), 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: