LeetCode --- 51. N-Queens
タイトルリンク: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:
この問題の要求はN皇后問題である:nの皇后をn*nの碁盤に置いて、任意の2人の皇后が互いに攻撃できないようにする.整数nが与えられ、「Q」は皇后を表し、「.」はすべての可能性を返す.空の位置を表します.
2人の皇后は互いに攻撃することができず、つまりこの2人の皇后が同じ行、同じ列、同じ斜線にいないことを要求した.
N皇后問題は、非常に古典的な問題であり、NP問題は、サブ問題を再帰的に処理することを主な考え方とし、以前のSudoku Solver問題と似ている.碁盤上の現在の行に1つの皇后を置くたびに、その行にすべての状況を列挙する必要があり、前の行の皇后と衝突しない場合、残りの位置を再帰的に処理することができます.前行数が最後の行を超えると、結果が保存され、再帰的に終了します.
重要な問題は、ある行の列に皇后を配置したときに衝突が発生したかどうかをどのように検出するかです.
1つのn*nの配列をマークとして、1つの皇后を置くときに、それに対応する行、列、斜線を皇后を置くことができない状態に置くことができ、1つの皇后を置くときに、その位置が衝突するかどうかを直接判断することができます.しかし,このような空間的複雑度は比較的高い(O(n 2)).
実際には,各行に1個のクイーンしか配置できないため,1個の長さnの整形配列を用いて各行のクイーンの位置を記録することができ,空間的複雑度をO(n)に低下させることができる.この場合,現在位置の皇后が以前の皇后と衝突しているかどうかを調べる際には,衝突していないかどうかを検出するために,以前の皇后を遍歴する必要がある.行ごとに再帰するため、皇后が同じ行にいないことが制限されているため、列値が同じかどうか、行列差の絶対値が同じかどうかを検出するだけである(同じ斜線にあるか否かを判断する).
時間複雑度:O(??)
空間複雑度:O(n)
転載は出典を説明してください:LeetCode---51.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.."]
]
この問題の要求はN皇后問題である:nの皇后をn*nの碁盤に置いて、任意の2人の皇后が互いに攻撃できないようにする.整数nが与えられ、「Q」は皇后を表し、「.」はすべての可能性を返す.空の位置を表します.
2人の皇后は互いに攻撃することができず、つまりこの2人の皇后が同じ行、同じ列、同じ斜線にいないことを要求した.
N皇后問題は、非常に古典的な問題であり、NP問題は、サブ問題を再帰的に処理することを主な考え方とし、以前のSudoku Solver問題と似ている.碁盤上の現在の行に1つの皇后を置くたびに、その行にすべての状況を列挙する必要があり、前の行の皇后と衝突しない場合、残りの位置を再帰的に処理することができます.前行数が最後の行を超えると、結果が保存され、再帰的に終了します.
重要な問題は、ある行の列に皇后を配置したときに衝突が発生したかどうかをどのように検出するかです.
1つのn*nの配列をマークとして、1つの皇后を置くときに、それに対応する行、列、斜線を皇后を置くことができない状態に置くことができ、1つの皇后を置くときに、その位置が衝突するかどうかを直接判断することができます.しかし,このような空間的複雑度は比較的高い(O(n 2)).
実際には,各行に1個のクイーンしか配置できないため,1個の長さnの整形配列を用いて各行のクイーンの位置を記録することができ,空間的複雑度をO(n)に低下させることができる.この場合,現在位置の皇后が以前の皇后と衝突しているかどうかを調べる際には,衝突していないかどうかを検出するために,以前の皇后を遍歴する必要がある.行ごとに再帰するため、皇后が同じ行にいないことが制限されているため、列値が同じかどうか、行列差の絶対値が同じかどうかを検出するだけである(同じ斜線にあるか否かを判断する).
時間複雑度:O(??)
空間複雑度:O(n)
1 class Solution
2 {
3 vector<vector<string> > vvs;
4
5 public:
6 vector<vector<string> > solveNQueens(int n)
7 {
8 vector<int> vi(n);
9 solveNQueens(vi, n, 0);
10 return vvs;
11 }
12
13 private:
14 void solveNQueens(vector<int> &vi, int n, int c)
15 {
16 if(c == n)
17 {
18 vector<string> vs(n, string(n, '.'));
19 for(int i = 0; i < n; ++ i)
20 vs[i][vi[i]] = 'Q';
21 vvs.push_back(vs);
22 return;
23 }
24
25 for(vi[c] = 0; vi[c] < n; ++ vi[c])
26 if(safe(vi, n, c))
27 solveNQueens(vi, n, c + 1);
28 }
29
30 bool safe(vector<int> &vi, int n, int c)
31 {
32 for(int i = 0; i < c; ++ i)
33 if(vi[i] == vi[c] || abs(vi[c] - vi[i]) == abs(c - i))
34 return false;
35 return true;
36 }
37 };転載は出典を説明してください:LeetCode---51.N-Queens