2016年12月12日 星期一

[LeetCode] 51. N-Queens

轉自LeetCode

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.."]
]
<Solution>

經典的 recursive 題目,解法就是用 DFS

有幾個小技巧 (參考資料)
  • 如果(row1,col1)和(row2,col2)在同個對角線上的話,abs(row1 - row2) = abs(col1 - col2)
  • 不需要用二維陣列來存Q放的位置,用一維陣列即可。state[i] 存放的是在第 i 列(row),Q放的 col。例如 state[4] = 2,代表 row 4,Q放的位置在 col 2。因此,檢查 row k 是不是可以放在某個 col,只要檢查 row 0 到 row k-1 的值有沒有等於 col 就可以了
另外,在參考資料裡面,還有提到一個神解

用到 bit  mask 的概念,有空可以看一下

recursive 解法如下

class Solution {
private:
vector<vector<string>> ans;
public:
vector<vector<string>> solveNQueens(int n) {
vector<int> state(n, -1);
dfs(0, state);
return ans;
}
void dfs(const int &row, vector<int> &state) {
int n = state.size();
//> find an answer, ending condition
if(row == n) {
//> has one answer
vector<string> tmpAns(n, string(n, '.'));
for(int i = 0; i < n; i++) {
tmpAns[i][state[i]] = 'Q';
}
ans.push_back(tmpAns);
return;
}
//> find possible answer
for(int c = 0; c < n; c++) {
if(isValid(row, c, state)) {
state[row] = c;
dfs(row+1, state);
state[row] = -1;
}
}
}
bool isValid(const int &row, const int &col, const vector<int> &state) {
for(int r = 0; r < row; r++) {
if(state[r] == col || abs(row - r) == abs(col - state[r])) {
return false;
}
}
return true;
}
};
view raw nQueens.cpp hosted with ❤ by GitHub

沒有留言:

張貼留言