Question

In: Computer Science

t is N queens problem please complete it //*************************************************************** // D.S. Malik // // This class...

t is N queens problem please complete it

//***************************************************************
// D.S. Malik
//
// This class specifies the functions to solve the n-queens
// puzzle.
//***************************************************************

class nQueensPuzzle
{
public:
nQueensPuzzle(int queens = 8);
//constructor
//Postcondition: noOfSolutions = 0; noOfQueens = queens;
// queensInRow is a pointer to the array
// that store the n-tuple.
// If no value is specified for the parameter queens,
// the default value, which is 8, is assigned to it.
bool canPlaceQueen(int k, int i);
//Function to determine whether a queen can be placed
//in row k and column i.
//Postcondition: returns true if a queen can be placed in
// row k and column i; otherwise it returns false

void queensConfiguration(int k);
//Function to determine all solutions to the n-queens
//puzzle using backtracking.
//The function is called with the value 0.
//Postcondition: All n-tuples representing solutions of
// n-queens puzzle are generated and printed.

void printConfiguration();
//Function to output an n-tuple containing a solution
//to the n-queens puzzle.

int solutionsCount();
//Function to return the total number of solutions.
//Postcondition: The value of noOfSolution is returned.

private:
int noOfSolutions;
int noOfQueens;
int *queensInRow;
};



#include <iostream>
#include <cmath>
#include "nQueenPuzzle.h"
using namespace std;

nQueensPuzzle::nQueensPuzzle()
{
noOfQueens = 8;
queensInColumn = new int[8];
noOfSolutions = 0;
}

nQueensPuzzle::nQueensPuzzle(int queens)
{
noOfQueens = queens;
queensInColumn = new int[noOfQueens];
noOfSolutions = 0;
}

bool nQueensPuzzle::canPlaceQueen(int k, int i)
{
for(int j = 0; j < k; j++)
if((queensInColumn[j] == i)
|| (abs(queensInColumn[j] - i) == abs(j-k)))
return false;
return true;
}

void nQueensPuzzle::queensConfiguration(int k)//, int queens)
{
for(int i = 0; i < noOfQueens; i++)
{
if(canPlaceQueen(k, i))
{
queensInColumn[k] = i;
if(k == noOfQueens - 1)
printConfiguration();
else
queensConfiguration(k + 1);
}
}
}

void nQueensPuzzle::printConfiguration()
{
noOfSolutions++;
cout<<"(";
for(int i = 0; i < noOfQueens - 1; i++)
cout<<queensInColumn[i]<<", ";


cout<<queensInColumn[noOfQueens - 1]<<")"<<endl;
}

int nQueensPuzzle::solutionsCount()
{
return noOfSolutions;
}

Solutions

Expert Solution

Working code implemented in C++ and appropriate comments provided for better understanding.

Here I am attaching code for all files:

main.cpp:

#include <iostream>
#include <fstream>
#include "nQueenPuzzle.h"

int main() {

   int max = 10;
   std::ofstream output;
   output.open("output.txt");

   for (int i = 0; i < max; i++) {
       nQueensPuzzle queens(i + 1);

       output << "\t\tBOARD " << i + 1 << "x" << i + 1 << "\n\n";

       queens.queensConfiguration(0, output);

       std::cout << "A " << i + 1 << "x" << i + 1 << " board has ";
       std::cout << queens.solutionsCount();
       std::cout << " solutions.\n";

       output << "\nA " << i + 1 << "x" << i + 1 << " board has ";
       output << queens.solutionsCount();
       output << " solutions.\n\n";
   }

   std::cout << "Output has been saved to output.txt because large numbers output too many lines.\n";

   output.close();

   return 0;
}

nQueenPuzzle.cpp:

#include <iostream>
#include <fstream>
#include <cmath>
#include "nQueenPuzzle.h"

nQueensPuzzle::nQueensPuzzle(int queens) {
   noOfQueens = queens;
   queensInRow = new int[noOfQueens];
   noOfSolutions = 0;
}

bool nQueensPuzzle::canPlaceQueen(int k, int i) {
   for (int j = 0; j < k; j++) {
       if ((queensInRow[j] == i) || (abs(queensInRow[j] - i) == abs(j-k))) {
           return false;
       }
   }
   return true;
}

void nQueensPuzzle::queensConfiguration(int k, std::ofstream &output) {
   for (int i = 0; i < noOfQueens; i++) {
       if (canPlaceQueen(k, i)) {
           queensInRow[k] = i;
           if (k == noOfQueens - 1) {
               printConfiguration(output);
           } else {
               queensConfiguration(k + 1, output);
           }
       }
   }
}

void nQueensPuzzle::printConfiguration(std::ofstream &output) {
   noOfSolutions++;
   output << "(";
   for (int i = 0; i < noOfQueens - 1; i++) {
       output << queensInRow[i] << ", ";
   }

   output << queensInRow[noOfQueens - 1] << ")\n";
}

int nQueensPuzzle::solutionsCount() {
   return noOfSolutions;
}
nQueensPuzzle.h:

#include <fstream>

class nQueensPuzzle {
public:
   nQueensPuzzle(int queens = 8);
   bool canPlaceQueen(int k, int i);
   void queensConfiguration(int k, std::ofstream &output);
   void printConfiguration(std::ofstream &output);
   int solutionsCount();
private:
   int noOfSolutions;
   int noOfQueens;
   int *queensInRow;
};

Sample Output Screenshots:


Related Solutions

I t is N queens problem please complete it //*************************************************************** // D.S. Malik // // This...
I t is N queens problem please complete it //*************************************************************** // D.S. Malik // // This class specifies the functions to solve the n-queens // puzzle. //*************************************************************** class nQueensPuzzle { public: nQueensPuzzle(int queens = 8); //constructor //Postcondition: noOfSolutions = 0; noOfQueens = queens; // queensInRow is a pointer to the array // that store the n-tuple. // If no value is specified for the parameter queens, // the default value, which is 8, is assigned to it. bool canPlaceQueen(int k,...
complete sudoku problem //*************************************************************** // D.S. Malik // // This class specifies the functions to solve...
complete sudoku problem //*************************************************************** // D.S. Malik // // This class specifies the functions to solve a sudoku problem. //*************************************************************** class sudoku { public: sudoku(); //default constructor //Postcondition: grid is initialized to 0 sudoku(int g[][9]); //constructor //Postcondition: grid = g void initializeSudokuGrid(); //Function to promt the user to specify the numbers of the //partially filled grid. //Postcondition: grid is initialized to the numbers // specified by the user. void initializeSudokuGrid(int g[][9]); //Function to initialize grid to g //Postcondition: grid =...
The N-QUEENS PROBLEM Given a chess board having N x N cells, we need to place...
The N-QUEENS PROBLEM Given a chess board having N x N cells, we need to place N queens in such a way that no queen is attacked by any other queen. A queen can only attack horizontally, vertically and diagonally. Let’s go at this one step at a time. let’s place the first Queen at some cell, (I, j) and now the number of unattackable cells are reduced. And now, the number of the Queens to be placed are N...
please complete the header file that contains a class template for ADT Queue and complete all...
please complete the header file that contains a class template for ADT Queue and complete all the member functions in the class template. Submit the header file only, but please write a source file that tests all the member functions to make sure they are working correctly. queue.h #ifndef _QUEUE #define _QUEUE #include"Node.h" template<class ItemType> class Queue { private:    Node<ItemType> *backPtr;    Node<ItemType> *frontPtr; public:    Queue(); //Default constructor    Queue(const Queue<ItemType> &aQueue);    bool isEmpty() const;    bool...
The Eight Queens Problem is a fairly old problem that has been well discussed and researched....
The Eight Queens Problem is a fairly old problem that has been well discussed and researched. The first published reference to this problem was in a German Chess magazine in 1848 by Max Bezzel. In 1850, Franz Nauck published all 92 solutions of the problem for an 8x8 board. S. Gunther in 1874 suggested a method for finding solutions by using determinants and J.W.L. Glaisher extended this method. E. Dijkstra published a detailed description of the solution of the problem...
Complete the "dumb" 8 queens program that Use the 1 dimensional array representation. C++ This is...
Complete the "dumb" 8 queens program that Use the 1 dimensional array representation. C++ This is the solution to the  question. i want this program to written in different WAY. nothing fancy. #include<cmath> #include<fstream> #include<iostream> using namespace std; bool ok(int b[][8]){ int rQueens=0, dQueens=0; for(int row=0; row<8; row++){ for(int column=0; column<8; column++){ //Rows test if(b[row][column]==1) rQueens++; if(rQueens>1) return false; //Diagonals test    for(int j=1; ((column-j)>=0)&&((row-j)>=0); j++){ if(b[row-j][column-j]==1&&b[row][column]==1) return false; } for(int k=1; ((column-k)>=0)&&((row+k)<8); k++){ if(b[row+k][column-k]==1&&b[row][column]==1) return false; } } rQueens=0; }...
- Solve the following recurrence relation : T(n) = T(αn) + T((1 − α)n) + n
- Solve the following recurrence relation : T(n) = T(αn) + T((1 − α)n) + n
In this case study, your task is to study different search algorithms to solve the N-Queens...
In this case study, your task is to study different search algorithms to solve the N-Queens Problem which has been presented in class. We will focus on the incremental formulation in which we add a queen to any square in the leftmost empty column that is not attacked by any other queen. We will compare the following algorithms: 1- Breadth-first Seatch (BFS) 2- Depth-first Search (DFS) 3- Simulated Annealing (SA) 4- Hill Climbing (HC) Question is:. Using any of the...
Complete the 8 queens 1 dimensional array program with backtracking in c+++. (don't use go to...
Complete the 8 queens 1 dimensional array program with backtracking in c+++. (don't use go to statement ) and please describe all the code statement and show the code in complier and also which can be copied. thank you very much
Use recursion tree to solve the recurrence: T(n) = T(n/15) + T(n/10) + 2T(n/6) + n^(1/2)
Use recursion tree to solve the recurrence: T(n) = T(n/15) + T(n/10) + 2T(n/6) + n^(1/2)
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT