Write a program that places eight queens on a chessboard so that none of them is attacking each other. Additionally, you must handle the situation where some queens have already been placed on the board. If this is the case then you need to place the rest of them so that there are totally eight(8) queens on the board. Your program must report all the possible solutions as there can be many of them. On the other hand, there may be none.
- The chessboard consists of 8x8 squares(see the picture). Each square may or may not contain a queen.
- Two queens are attacking each other if they occupy the same row, column or diagonal.
Your solution is a header file named "chessqueens.h". It contains a function which solves the problem (Do not place function declaration in your code - only the definition). Remember to read the rules.
The prototype of the function is:
- Code: Select all
void solveboard(const std::vector<short int> &board, std::vector<std::vector<short int> > &solution); // remember #include <vector>
INPUT
- const std::vector<short int> &board
An std::vector named "board" contains the coordinates of the queens already placed on the chessboard. One short integer in the vector represents one (x,y) position on the chessboard.
To get x and y coordinates of short int "n" in "board", use:
- Code: Select all
x = n>>3; // n is an integer in the "board" vector
y = n&7;
Both x and y coordinates will be encoded using operation n = (x<<3)|y when given as input to your program.
Constraints:
* For all elements e in "board", this equation holds: 0 <= e <= 63 , where e is one of board[0..board.size()-1]
(this means that
0 <= x,y < 8
where x and y are the coordinates of the given queens)
* board.size() <= 8
(there are at most 8 queens already placed for you)
OUTPUT
- std::vector<std::vector<short int> > &solution
"solution" must contain all the possible combinations of the eight queens' coordinates on the chessboard. Every element in "solution" must be different from the others. Two combinations are considered different if one or more coordinates are not found in both combinations. One std::vector<short int> contains one combination. This means that the number of correct combinations is equal to solution.size() when your function terminates.
Every vector in "solution" should have size() equal to 8.
* Before calling your function, solution.empty() == true (this should also be true at the termination of your function if there is no correct solution)
* You must encode your coordinates in the same way than you decode them in INPUT: n=(x<<3)|y;
For example, suppose you need to insert one queen in (x,y) to a combination c:
- Code: Select all
std::vector<short int> c; // Combination vector holds all 8 encoded coordinates
short int n = (x<<3)|y;
c.push_back(n); // add the first one of eight queens to c.
std::vector "solution" must contain every correct combination.
Send your solution in a file with name "chessqueens.h" as attachment to raimo@cpp-home.com. If you have any questions about the contest they should be posted in this thread.
Contest deadline: November 29th, 2003.
This is a beginner(/intermediate?) contest.
Optimize for speed.
)
Beginner contest is a beginner contest, though. 
)
