/* ** *** @üťhöř : Řëwä Mąťhúŕ @Śťaťüš : Sťïľľ Ïñ Çöñšťŕūçťīöñ @Ďäťë : 18 Jäñ 2019 ** *** */ // this codes uses some concepts of dynamic programming approach like DFS algorithm, backtracking which really helps to get familiar with the dynamic programming required in the real life programming and improved your skills so get on an look up on an non web code which is always suffering from alonnenss😏 // uses C++11 threads to parallelize the computation; also uses backtracking // Outputs all solutions for any table size //threads and mutex are used in the creation of code so that it can leads to learn some concepts any query about the code make comment by pinging me will try to solve your query // Much shorter than the version below; // uses C++11 threads to parallelize the computation; also uses backtracking // Outputs all solutions for any table size #include #include #include #include #include // Print table. 'pos' is a vector of positions – the index in pos is the row, // and the number at that index is the column where the queen is placed. static void print(const std::vector &pos) { // print table header for (int i = 0; i < pos.size(); i++) { std::cout << std::setw(3) << char('a' + i); } std::cout << '\n'; for (int row = 0; row < pos.size(); row++) { int col = pos[row]; std::cout << row + 1 << std::setw(3 * col + 3) << " Q "; std::cout << '\n'; } std::cout << "\n\n"; } static bool threatens(int row_a, int col_a, int row_b, int col_b) { return row_a == row_b // same row or col_a == col_b // same column or std::abs(row_a - row_b) == std::abs(col_a - col_b); // diagonal } // the i-th queen is in the i-th row // we only check rows up to end_idx // so that the same function can be used for backtracking and checking the final solution static bool good(const std::vector &pos, int end_idx) { for (int row_a = 0; row_a < end_idx; row_a++) { for (int row_b = row_a + 1; row_b < end_idx; row_b++) { int col_a = pos[row_a]; int col_b = pos[row_b]; if (threatens(row_a, col_a, row_b, col_b)) { return false; } } } return true; } static std::mutex print_count_mutex; // mutex protecting 'n_sols' static int n_sols = 0; // number of solutions // recursive DFS backtracking solver static void n_queens(std::vector &pos, int index) { // if we have placed a queen in each row (i. e. we are at a leaf of the search tree), check solution and return if (index >= pos.size()) { if (good(pos, index)) { std::lock_guard lock(print_count_mutex); print(pos); n_sols++; } return; } // backtracking step if (not good(pos, index)) { return; } // optimization: the first level of the search tree is parallelized if (index == 0) { std::vector> fts; for (int col = 0; col < pos.size(); col++) { pos[index] = col; auto ft = std::async(std::launch::async, [=]{ auto cpos(pos); n_queens(cpos, index + 1); }); fts.push_back(std::move(ft)); } for (const auto &ft : fts) { ft.wait(); } } else { // deeper levels are not for (int col = 0; col < pos.size(); col++) { pos[index] = col; n_queens(pos, index + 1); } } } int main() { std::vector start(6); // 12: table size n_queens(start, 0); std::cout << n_sols << " solutions found.\n"; return 0; }

N-Queens Problem Solution With Traditional Approach