The objective of the programming assignment is to write a parallel...
Question
The objective of the programming assignment is to write a parallel program to solve the n-queens problem. Your solution should follow the following outline: We use the master-worker paradigm, where processor with rank 0 will act as the master processor and the rest of the processors act as workers. Processor 0 will initiate the search by starting to fill an array of positions as described before. However, whenever a specific depth k is reached, a copy of the array will be dispatched to one of the worker processors. The worker processor will explore all the remaining possible combinations and report any solution(s) found to the master processor. As soon as the task is dispatched, the master processor will continue by exploring the next position on the same column etc. to generate another task and dispatch it.
One can view the master processor as performing a search limited to the first k positions. Each worker processor will get a task with first, k positions filled and will perform a search for the remaining n — k positions. When a worker is done with its task, it will report the outcome and request more work. The master processor will continually dispatch work until all the tasks have been send out. At this stage, it will send a message to all workers to terminate. Then the master process will wait for remaining solutions, print out all found solutions and finally terminate itself.
Complete only the methods in mpi_nqueens.cpp.
One can view the master processor as performing a search limited to the first k positions. Each worker processor will get a task with first, k positions filled and will perform a search for the remaining n — k positions. When a worker is done with its task, it will report the outcome and request more work. The master processor will continually dispatch work until all the tasks have been send out. At this stage, it will send a message to all workers to terminate. Then the master process will wait for remaining solutions, print out all found solutions and finally terminate itself.
Complete only the methods in mpi_nqueens.cpp.
Solution Preview
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references.
Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.
/**
* @file nqueens.cpp
* @brief Implements the functions for solving the nqueens problem in.
*
*/
#include "nqueens.h"
#include <cmath>
/*********************************************************************
* Implement your solutions here! *
*********************************************************************/
/**
* @brief Generates the solutions for the n-queen problem in a specified range.
*
*
* This function will search for all valid solutions in the range
* [start_level,max_level). This assumes that the partial solution for levels
* [0,start_level) is a valid solution.
*
* The master and the workers will both use this function with different parameters.
* The master will call the function with start_level=0 and max_level=k, and the
* workers will call this function with start_level=k and max_level=n and their
* received partial solution.
*
* For every valid solution that is found, the given callback function is called
* with the current valid solution as parameter.
*
* @param pos A vector of length n that contains the partial solution
* for the range [0, start_level).
* @param start_level Gives the level at which the algorithm will start to
* generate solutions. The solution vector `pos` is assumed
* to have a valid solution for positions [0,start_level-1].
* @param max_level The level at which the algorithm will stop and pass
* the current valid solution to the callback function.
* @param success_func A callback function that is called whenever a valid
* solution of `max_level` levels is found. The found
* solution is passed as parameter to this callback function.
*/
void nqueens_by_level(std::vector<unsigned int> pos, unsigned int start_level, unsigned int max_level, void(*const success_func)(std::vector<unsigned int>&)) {
int n = pos.capacity();
int k = start_level;
bool place(int k, int i){ // Function that returns true or false depending on wether queen can or can't be placed at position (k,i)
for (int j = 0; j < k - 1; j++){
if ((pos[j] == i) || (abs(j - k) == abs(pos[j] - i)){ return false; }
}
return true;
}
std::vector<unsigned int> stack;
stack.push_back(0);
while (!stack.empty()){
for (int j = stack.back(); j < n; j++){
if (place(k, j)){
stack.pop_back();
pos[k] = j;
if (k == max_level){ succes_func(pos); }
else{ stack.push_back(j+1); k = k + 1; stack.push_back(0); break; }
}
}
k = k - 1; stack.pop_back();
}
}
/*********************************************************************
* You don't have to change anything beyond this point *
*********************************************************************/
// stores all local solutions.
struct SolutionStore {
// store solutions in a static member variable
static std::vector<unsigned int>& solutions() {
static std::vector<unsigned int> sols;
return sols;
}
static void add_solution(const std::vector<unsigned int>& sol) {
// add solution to static member
solutions().insert(solutions().end(), sol.begin(), sol.end());
}
static void clear_solutions() {
solutions().clear();
}
};
// callback for generating local solutions
void add_solution_callback(std::vector<unsigned int>& solution) {
SolutionStore::add_solution(solution);
}
// returns all solutions to the n-Queens problem, calculated sequentially
// This function requires that the nqueens_by_level function works properly.
std::vector<unsigned int> nqueens(unsigned int n) {
std::vector<unsigned int> zero(n, 0);
nqueens_by_level(zero, 0, n, &add_solution_callback);
std::vector<unsigned int> allsolutions = SolutionStore::solutions();
SolutionStore::clear_solutions();
return allsolutions;
}
* @file nqueens.cpp
* @brief Implements the functions for solving the nqueens problem in.
*
*/
#include "nqueens.h"
#include <cmath>
/*********************************************************************
* Implement your solutions here! *
*********************************************************************/
/**
* @brief Generates the solutions for the n-queen problem in a specified range.
*
*
* This function will search for all valid solutions in the range
* [start_level,max_level). This assumes that the partial solution for levels
* [0,start_level) is a valid solution.
*
* The master and the workers will both use this function with different parameters.
* The master will call the function with start_level=0 and max_level=k, and the
* workers will call this function with start_level=k and max_level=n and their
* received partial solution.
*
* For every valid solution that is found, the given callback function is called
* with the current valid solution as parameter.
*
* @param pos A vector of length n that contains the partial solution
* for the range [0, start_level).
* @param start_level Gives the level at which the algorithm will start to
* generate solutions. The solution vector `pos` is assumed
* to have a valid solution for positions [0,start_level-1].
* @param max_level The level at which the algorithm will stop and pass
* the current valid solution to the callback function.
* @param success_func A callback function that is called whenever a valid
* solution of `max_level` levels is found. The found
* solution is passed as parameter to this callback function.
*/
void nqueens_by_level(std::vector<unsigned int> pos, unsigned int start_level, unsigned int max_level, void(*const success_func)(std::vector<unsigned int>&)) {
int n = pos.capacity();
int k = start_level;
bool place(int k, int i){ // Function that returns true or false depending on wether queen can or can't be placed at position (k,i)
for (int j = 0; j < k - 1; j++){
if ((pos[j] == i) || (abs(j - k) == abs(pos[j] - i)){ return false; }
}
return true;
}
std::vector<unsigned int> stack;
stack.push_back(0);
while (!stack.empty()){
for (int j = stack.back(); j < n; j++){
if (place(k, j)){
stack.pop_back();
pos[k] = j;
if (k == max_level){ succes_func(pos); }
else{ stack.push_back(j+1); k = k + 1; stack.push_back(0); break; }
}
}
k = k - 1; stack.pop_back();
}
}
/*********************************************************************
* You don't have to change anything beyond this point *
*********************************************************************/
// stores all local solutions.
struct SolutionStore {
// store solutions in a static member variable
static std::vector<unsigned int>& solutions() {
static std::vector<unsigned int> sols;
return sols;
}
static void add_solution(const std::vector<unsigned int>& sol) {
// add solution to static member
solutions().insert(solutions().end(), sol.begin(), sol.end());
}
static void clear_solutions() {
solutions().clear();
}
};
// callback for generating local solutions
void add_solution_callback(std::vector<unsigned int>& solution) {
SolutionStore::add_solution(solution);
}
// returns all solutions to the n-Queens problem, calculated sequentially
// This function requires that the nqueens_by_level function works properly.
std::vector<unsigned int> nqueens(unsigned int n) {
std::vector<unsigned int> zero(n, 0);
nqueens_by_level(zero, 0, n, &add_solution_callback);
std::vector<unsigned int> allsolutions = SolutionStore::solutions();
SolutionStore::clear_solutions();
return allsolutions;
}
This is only a preview of the solution.
Please use the purchase button to see the entire solution.
Please use the purchase button to see the entire solution.
By purchasing this solution you'll be able to access the following files:
solution.zip
Purchase Solution
$70.00
$35
View Available
Computer Science Tutors 529 tutors matched
Ionut
(ionut)
Hi! MSc Applied Informatics & Computer Science Engineer. Practical experience in many CS & IT branches.Research work & homework
5/5 (5,654+ sessions)
2 hours avg response
Leo
(Leo)
Hi!
I have been a professor in New York and taught in a math department and in an applied math department.
4.9/5 (5,652+ sessions)
2 hours avg response
Pranay
(math1983)
Ph.D. in mathematics and working as an Assistant Professor in University. I can provide help in mathematics, statistics and allied areas.
4.6/5 (5,512+ sessions)
1 hour avg response