58. N-Queens && N-Queens II

N-Queens

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.."]
]
思路： 简单题。全排列。（注意各行各列不同可以直接确定住）

void getSolution(veor<int> &r, vector<vector<string> > &vec) {
    int n = r.size();
    vector<string> vec2;
    for(int i = 0; i < n; ++i) {
        vec2.push_back(string(n, '.'));
        vec2[i][r[i]] = 'Q';
    }
    vec.push_back(vec2);
}

bool judge(vector<int> &r) {
    for(size_t i = 0; i < r.size(); ++i) 
        for(size_t j = i+1; j < r.size(); ++j) 
            if(j-i == r[j]-r[i] || j-i == r[i]-r[j])
                return false;
    return true;
}

void getPosition(int cur, vector<int> &r, vector<vector<string> > &vec) {
    if(cur == r.size()) {
        if(judge(r)) 
            getSolution(r, vec);
        return;
    }
    for(int e = cur; e < r.size(); ++e) {
        int t = r[cur];
        r[cur] = r[e];
        r[e] = t;
        getPosition(cur+1, r, vec);
        r[e] = r[cur];
        r[cur] = t;
    }
}

class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string> > vec;
        if(n <= 0) return vec;
        vector<int> r(n);
        for(int i = 0; i < n; ++i) r[i] = i;
        getPosition(0, r, vec);
        return vec;
    }
};

 

N-Queens II

Follow up for N-Queens problem.

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

思路： 比上题好像更简单一些。

bool judge(vector<int> &r) {
    for(size_t i = 0; i < r.size(); ++i) 
        for(size_t j = i+1; j < r.size(); ++j) 
            if(j-i == r[j]-r[i] || j-i == r[i]-r[j])
                return false;
    return true;
}
void getPosition(int cur, vector<int> &r, int &cnt) {
    if(cur == r.size()) {
        if(judge(r)) 
            ++cnt;
        return;
    }
    for(int e = cur; e < r.size(); ++e) {
        int t = r[cur];
        r[cur] = r[e];
        r[e] = t;
        getPosition(cur+1, r, cnt);
        r[e] = r[cur];
        r[cur] = t;
    }
}
class Solution {
public:
    int totalNQueens(int n) {
        if(n <= 0) return 0;
        int cnt = 0;
        vector<int> r(n);
        for(int i = 0; i < n; ++i) r[i] = i;
        getPosition(0, r, cnt);
        return cnt;
    }
};

 可参考剑指 offer:题28