n皇后 最快算法_n皇后dp

这是一种状态压缩 dp
1、 求 n 皇后总数

class Solution {
public:
    int upperlimit = 0;
    int sum = 0;
	
	/*
		从第一行开始能放的位置， 并置为 1
		now 记录了当前哪些列放了皇后
		ld 记录了 45 度方向放皇后的列
		rd 记录了 135 度方向放皇后的列
	*/
    void test(int now, int left, int right) {
        if (now == upperlimit) {
            ++sum;
            return;
        }
        if (now != upperlimit) {
        	// 找到当前行哪些列可放皇后
            int pos  = upperlimit &  ~ (now | left | right);
            while (pos) {
            	// 找到最右的位置
                int  p = pos & -pos;
                //将当前列置为 1， 递归寻找下一行
                test(now ^ p, (left ^ p) << 1, (right ^ p) >> 1);
                pos -= p;
            }
        }
    }

    int totalNQueens(int n) {
        upperlimit = (1 << n) - 1;
        sum = 0;
        test(0, 0, 0);
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

2. 求有哪些 n 皇后

/*
 * @lc app=leetcode.cn id=51 lang=cpp
 *
 * [51] N 皇后
 */
#include <iostream>
#include <utility>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>

using namespace std;

// @lc code=start
class Solution {
public:
    bool valid(vector<string>& temp, int x, int y) {
        // 列
        for (int i = 0; i < x; ++i) {
            if (temp[i][y] == 'Q') {
                return false;
            }
        }
        // 45°
        int nx = x - 1, ny = y + 1;
        while (nx >= 0 && ny < temp[0].size()) {
            if (temp[nx][ny] == 'Q') {
                return false;
            }
            nx = nx - 1;
            ny = ny + 1;
        }

        // 135°
        nx = x - 1, ny = y - 1;
        while (nx >= 0 && ny >= 0) {
            if (temp[nx][ny] == 'Q') {
                return false;
            }
            nx = nx - 1;
            ny = ny - 1;
        }
        return true;
    }

    void backtracking(vector<vector<string>>& ans, vector<string>& temp, int row) {
        if (row >= temp.size()) {
            ans.push_back(temp);
            return;
        }
        for (int i = 0; i < temp[0].size(); ++i) {
            if (valid(temp, row, i)) {
                temp[row][i] = 'Q';
                backtracking(ans, temp, row + 1);
                temp[row][i] = '.';
            }
        }
    }
	
	/*
		一般回溯寻找
	*/
    vector<vector<string>> solveNQueens1(int n) {
        vector<string> temp(n, string(n, '.'));
        vector<vector<string>> ans;
        backtracking(ans, temp, 0);
        return ans;
    }
	
    void backtracking_plus(vector<vector<string>>& ans, vector<string>& temp, int i, int now, int ld, int rd, int upperlimt) {
        if (now == upperlimt) {
            ans.push_back(temp);
            return;
        }
        int pos = upperlimt & ~(now | ld | rd);
        while (pos) {
            int p = pos & ~(pos - 1);
            pos -= p;
            int index = log2(p);
            temp[i][index] = 'Q';
            backtracking_plus(ans, temp, i + 1, now ^ p, (ld ^ p) << 1, (rd ^ p) >> 1, upperlimt);
            temp[i][index] = '.';
        }
    }
	
	/*	
		优化回溯算法
	*/
    vector<vector<string>> solveNQueens(int n) {
        vector<string> temp(n, string(n, '.'));
        vector<vector<string>> ans;
        backtracking_plus(ans, temp,0, 0, 0, 0, pow(2, n) - 1);
        return ans;
    }
};
// @lc code=end

int main() {
    auto data = Solution{}.solveNQueens(6);
    for (auto& strvec : data) {
        for (auto& str : strvec) {
            cout << str << endl;
        }
        cout << endl;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116