Poor Man\'s N-Queens Problem n queens are to be arranged on an n x n chessboard
ID: 3621192 • Letter: P
Question
Poor Man's N-Queens Problemn queens are to be arranged on an n x n chessboard in such a way that no queen checks another queen; that is, no two queens may be placed on the same row, on the same column or along the same diagonal of the board. finding all solutions to this n queens problem is non trivial no analytic solution exists, although backtracking and gradient - and constraint propagation-based heuristic techniques can be used in the solution of the general problem ( and similar ones).
There does exist, however a well-known explicit solution that yields a single solution to the problem for all n > 3. The algorithm is as follows:
Let (i,j) denote the square on the row i and column j (1 <= i, j <= n). Depending on the value of n, there are three cases:
1. n is even but not of the form (n mod 6 = 2).
Place queens on the squares
(m, 2m) and (n/2 +m, 2m-1) for m = 1, 2, . . . , n/2
1. n is even but not of the form (n mod 6 = 0) and
Place queens on the squares
(m, 1+(2(m-1)+ n/2 - 1)mod n) and
(n+1-m, n-(2(m-1)+n/2 -1)mod n) for m = 1,2,...,n/2
3. n is odd.
Use (1) or (2), whichever is appropriate, on n - 1 and extend with a queen at (n,n).
Write a C++ implementation in a file called NQueensProblemSingleSolution.cc of a class NQueensProblemSingleSolution containing two member fields (instance variables)
1. n, an int, and
2. solutionVector, an n-element, dynamically-allocated, one-dimensional int array whose jth element represents the row in which the queen in the jth column is tobe placed in the single explicit solution to the problem.
and two public member functions: a constructor that takes the value of n as its argument, and an overload << operator which produces output representing the solution as a set of 0-based ordered pairs in the form:
{(r1, c1), (r2,c2),...,(rn,cn)}
(92 solutions exist for an 8x8 chessboard including rotational and reflective equivalents.)
#ifndef NQUEENSPROBLEMSINGLESOLUTION_H
#define NQUEENSPROBLEMSINGLESOLUTION_H
#include <iostream>
using namespeace std;
class NQueensProblemSingleSolution {
private:
int n;
int *solutionVector;
public:
NQueensProblemSingleSolution(int numberOfQueens);
NQueensProblemSingleSolution(const NQueensProblemSingleSolution& solution);
~ NQueensProblemSingleSolution();
NQueensProblemSingleSolution& operator=(const NQueensProblemSingleSolution& rhs);
friend ostream& operator <<(ostream& out const NQueensProblemSingleSolution& solution);
};
#endif
Since C++ uses 0-based arrays, the values generated by the formulas above which assume values of 1 through n-- will be decremented; in fact, if i and j are row and column positions generated using the formulas, the assignment to the solution vector might be done as:
solutionVector[--j]= --i;
As examples of the n-queens calculation, consider
n= 6:
m1=
m1= (1,2),(4,1) m2 = (2,4),(5,3) m3 = (3,6),(6,5)
solutionVector will then contain {3,0,4,1,5,2} (The sequence of values generated by the formulas being (4,1,5,2,6,3,7).
n = 7:
m1= (1,2),(4,1) m2= (2,4),(5,3) m=3 (3,6),(6,5),(7,7)
solutionVector will then contain {3,0,4,1,5,2,6} (The sequence of values generated by the formulas being (1,5,2,6,3,7).
n = 8:
m1 = (1,4),(8,5) m2= (2,6),(7,3) m3 = (3,8),(6,1) m4=(4,2),(5,7)
solutionVector will the contain {5,3,6,0,7,1,4,2}. (The sequence of values generated by the formulas being {6,4,7,1,8,2,5,3}
I don't really understand what i's suppose to put for the int main. I think I have my implementation file right, with the constructors, deconstructors and overloading. If you want to see my implementation file, just email me and ill send it.
Thank you so much for taking the time to read this and work on it also it will be a great help in my understanding.