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:
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 解法如下
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
}; |
沒有留言:
張貼留言