debianforum.de

nqueens_cc

SNIPPET_DESC:

Optimierte c++-Version

SNIPPET_CREATION_TIME:

21.12.2024 05:45:09

SNIPPET_PRUNE_TIME:

Unendlich

SNIPPET_TEXT:

1. #include <iostream>
2. #include <vector>
3. #include <stdexcept>
4. #include <string>
5. #include <limits>
6. #include <thread>
7. #include <future>
8.  
9. using namespace std;
10.  
11. //External bitbanging to keep the solve()-function mostly as it is.
12. typedef uint64_t inttype;  //yes, works "only" until n=32 but gcc has __int128. There is  uint265_t from immintrin.h and uint512_t from boost...
13. class BoolArr {
14.     inttype arr=0;
15.     public:
16.     inline void set(int n) {
17.         arr|=1<<n;
18.     }
19.     inline void unset(int n) {
20.         arr&=~(1<<n);
21.     }
22.     inline int get(int n){
23.         return (arr>>n)&1;
24.     }
25. };
26. int solve(const int row, const int n, BoolArr lockCol, BoolArr lockLtrb, BoolArr lockRtlb) {
27.     int count=0;
28.     if (row < n) {
29.         for (int dx = 0; dx < n; dx++) {
30.             if (lockCol.get(dx) | lockLtrb.get(dx - row + n - 1) | lockRtlb.get(dx + row)) {
31.                 continue;
32.             }
33.             lockCol.set(dx);
34.             lockLtrb.set(dx - row + n - 1);
35.             lockRtlb.set(dx + row);
36.             count+=solve(row + 1, n, lockCol, lockLtrb, lockRtlb);
37.             lockCol.unset(dx);
38.             lockLtrb.unset(dx - row + n - 1);
39.             lockRtlb.unset(dx + row);
40.         }
41.         return count;
42.     } else {
43.         return 1;
44.     }
45. }
46. //parallel function for the first loop
47. int solve_p(const int row, const int n, BoolArr lockCol, BoolArr lockLtrb, BoolArr lockRtlb) {
48.     std::future<int> countn[n];
49.     if (row < n) {
50.         for (int dx = 0; dx < n; dx++) {
51.             if (lockCol.get(dx) | lockLtrb.get(dx - row + n - 1) | lockRtlb.get(dx + row)) {
52.                 continue;
53.             }
54.             lockCol.set(dx);
55.             lockLtrb.set(dx - row + n - 1);
56.             lockRtlb.set(dx + row);
57.             countn[dx]=std::async(launch::async|launch::deferred,&solve,row + 1, n, lockCol, lockLtrb, lockRtlb);
58.             lockCol.unset(dx);
59.             lockLtrb.unset(dx - row + n - 1);
60.             lockRtlb.unset(dx + row);
61.         }
62.         int count=0;
63.         for (int dx = 0; dx < n; dx++)
64.         {
65.             //if(countn[dx].valid())
66.             count+=countn[dx].get();
67.         }
68.         return count;
69.     } else {
70.         return 1;
71.     }
72. }
73.  
74. int main(int argc, char* argv[]) {
75.     int n = 10;
76.     if (argc != 2) {
77.         cout << "Usage: NQueens <board_size>" << endl;
78.         return 1;
79.     }
80.  
81.     try {
82.         n = stoi(argv[1]);
83.     } catch (invalid_argument&) {
84.         cout << "Invalid input! Board size must be a positive integer!" << endl;
85.         return 1;
86.     } catch (out_of_range&) {
87.         cout << "Invalid input! Board size is out of range!" << endl;
88.         return 1;
89.     }
90.  
91.     if (n <= 0||n>sizeof(inttype)*4) {
92.         cout << "Invalid input! Board size must be a positive integer!" << endl;
93.         return 1;
94.     }
95.  
96.     cout << "Solving: n=" << n << endl;
97.  
98.     BoolArr lockCol;
99.     BoolArr lockLtrb;
100.     BoolArr lockRtlb;
101.  
102.     int count = solve_p(0, n, lockCol, lockLtrb, lockRtlb);
103.  
104.     cout << "Result:  " << count << endl;
105.     return 0;
106. }

Quellcode

Hier kannst du den Code kopieren und ihn in deinen bevorzugten Editor einfügen. PASTEBIN_DOWNLOAD_SNIPPET_EXPLAIN