nqueens_cc
von wanne- SNIPPET_DESC:
- Optimierte c++-Version
- SNIPPET_CREATION_TIME:
- 21.12.2024 05:45:09
- SNIPPET_PRUNE_TIME:
- Unendlich
- SNIPPET_TEXT:
-
- #include <iostream>
- #include <vector>
- #include <stdexcept>
- #include <string>
- #include <limits>
- #include <thread>
- #include <future>
- using namespace std;
- //External bitbanging to keep the solve()-function mostly as it is.
- 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...
- class BoolArr {
- inttype arr=0;
- public:
- inline void set(int n) {
- arr|=1<<n;
- }
- arr&=~(1<<n);
- }
- inline int get(int n){
- return (arr>>n)&1;
- }
- };
- int solve(const int row, const int n, BoolArr lockCol, BoolArr lockLtrb, BoolArr lockRtlb) {
- if (row < n) {
- for (int dx = 0; dx < n; dx++) {
- if (lockCol.get(dx) | lockLtrb.get(dx - row + n - 1) | lockRtlb.get(dx + row)) {
- continue;
- }
- lockCol.set(dx);
- lockLtrb.set(dx - row + n - 1);
- lockRtlb.set(dx + row);
- }
- } else {
- return 1;
- }
- }
- //parallel function for the first loop
- int solve_p(const int row, const int n, BoolArr lockCol, BoolArr lockLtrb, BoolArr lockRtlb) {
- std::future<int> countn[n];
- if (row < n) {
- for (int dx = 0; dx < n; dx++) {
- if (lockCol.get(dx) | lockLtrb.get(dx - row + n - 1) | lockRtlb.get(dx + row)) {
- continue;
- }
- lockCol.set(dx);
- lockLtrb.set(dx - row + n - 1);
- lockRtlb.set(dx + row);
- countn[dx]=std::async(launch::async|launch::deferred,&solve,row + 1, n, lockCol, lockLtrb, lockRtlb);
- }
- for (int dx = 0; dx < n; dx++)
- {
- //if(countn[dx].valid())
- }
- } else {
- return 1;
- }
- }
- int main(int argc, char* argv[]) {
- int n = 10;
- if (argc != 2) {
- cout << "Usage: NQueens <board_size>" << endl;
- return 1;
- }
- try {
- n = stoi(argv[1]);
- } catch (invalid_argument&) {
- cout << "Invalid input! Board size must be a positive integer!" << endl;
- return 1;
- } catch (out_of_range&) {
- cout << "Invalid input! Board size is out of range!" << endl;
- return 1;
- }
- cout << "Invalid input! Board size must be a positive integer!" << endl;
- return 1;
- }
- cout << "Solving: n=" << n << endl;
- BoolArr lockCol;
- BoolArr lockLtrb;
- BoolArr lockRtlb;
- return 0;
- }
Quellcode
Hier kannst du den Code kopieren und ihn in deinen bevorzugten Editor einfügen. PASTEBIN_DOWNLOAD_SNIPPET_EXPLAIN