LeetCode - N-Queens
11620 단어 LeetCode
2014.2.13 19:23
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:
The Eight Queens problem is a typical model for backtracking algorithm.
For any pair of queens, their difference in x and y coordinates mustn't be 0 or equal, that's on the same row, column or diagonal line.
The code is short and self-explanatory, please see for yourself.
Total time complexity is O(n!). Space complexity is O(n!) as well, which comes from local parameters in recursive function calls.
Accepted code:
1 // 1CE, 1WA, 1AC, try to make the code shorter, it'll help you understand it better.
2 class Solution {
3 public:
4 vector<vector<string> > solveNQueens(int n) {
5 a = nullptr;
6 res.clear();
7 if (n <= 0) {
8 return res;
9 }
10
11 a = new int[n];
12 solveNQueensRecursive(0, a, n);
13 delete[] a;
14
15 return res;
16 }
17 private:
18 int *a;
19 vector<vector<string> > res;
20
21 void solveNQueensRecursive(int idx, int a[], const int &n) {
22 if (idx == n) {
23 // one solution is found
24 addSingleResult(a, n);
25 return;
26 }
27
28 int i, j;
29 // check if the current layout is valid.
30 for (i = 0; i < n; ++i) {
31 a[idx] = i;
32 for (j = 0; j < idx; ++j) {
33 if (a[j] == a[idx] || myabs(idx - j) == myabs(a[idx] - a[j])) {
34 break;
35 }
36 }
37 if (j == idx) {
38 // valid layout.
39 solveNQueensRecursive(idx + 1, a, n);
40 }
41 }
42 }
43
44 void addSingleResult(const int a[], int n) {
45 vector<string> single_res;
46 char *str = nullptr;
47
48 str = new char[n + 1];
49 int i, j;
50 for (i = 0; i < n; ++i) {
51 for (j = 0; j < n; ++j) {
52 str[j] = '.';
53 }
54 str[j] = 0;
55 str[a[i]] = 'Q';
56 single_res.push_back(string(str));
57 }
58
59 res.push_back(single_res);
60 single_res.clear();
61 delete []str;
62 }
63
64 int myabs(const int x) {
65 return (x >= 0 ? x : -x);
66 }
67 };
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.