## Contest 34: Eight Queens

Online C++ programming contests.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard, raimo

### Contest 34: Eight Queens

Contest 34: Eight Queens

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" vectory = 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 coordinatesshort 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.
This is a beginner(/intermediate?) contest.
Optimize for speed.
Last edited by raimo on Thu Jan 15, 2004 6:17 am, edited 2 times in total.

raimo

Posts: 372
Joined: Fri Sep 26, 2003 6:50 am
Location: Finland

There are exactly 8! solutions, 8!=1*2*3*4*5*6*7*8

Bay_Huy

Posts: 36
Joined: Mon Oct 20, 2003 3:02 pm

I forgot the diagonals:)

Bay_Huy

Posts: 36
Joined: Mon Oct 20, 2003 3:02 pm

8! - 2**(8-1) ( ** is FORTRAN pow )

Bay_Huy

Posts: 36
Joined: Mon Oct 20, 2003 3:02 pm

Bay_Huy wrote:Ok ready number of solutions:
8! - 2**(8-1) ( ** is FORTRAN pow )

Huh?? My compiler does not support smilies....

RecursiveS

Posts: 1236
Joined: Thu Sep 18, 2003 8:33 am
Location: Dorset, UK

You have a compiler?

Bay_Huy

Posts: 36
Joined: Mon Oct 20, 2003 3:02 pm

It's allowed to write other functions, but why aren't we (or are we) permitted to use classes. It's frustating to use tons of parameters instead of just using member variables.
egaga

Posts: 7
Joined: Sat Nov 15, 2003 12:34 pm
Location: Finland

egaga wrote:It's allowed to write other functions, but why aren't we (or are we) permitted to use classes. It's frustating to use tons of parameters instead of just using member variables.

I don't see why you couldn't be permitted to use classes. Of course you can.

Just keep the solution in one file like the description tells to do so that evaluating the codes is easier for me.

raimo

Posts: 372
Joined: Fri Sep 26, 2003 6:50 am
Location: Finland

raimo wrote:I don't see why you couldn't be permitted to use classes. Of course you can.

Great, I just thought it could be prohibited for some reason I couldn't think of.

raimo wrote:Just keep the solution in one file like the description tells to do so that evaluating the codes is easier for me.

Sure .

Only because of using a class, my program runs about 5 times faster .
egaga

Posts: 7
Joined: Sat Nov 15, 2003 12:34 pm
Location: Finland

Seems rather odd that you'd choose an 8x8 board considering there's only 12 different variation (if you disregard mirrored and rotated boards, which total 92). Wouldn't that make the fastest solution a simple lookup table, or since they may not be allowed an algorithmic representation of one?
Nexis

Nexis wrote:Seems rather odd that you'd choose an 8x8 board considering there's only 12 different variation (if you disregard mirrored and rotated boards, which total 92). Wouldn't that make the fastest solution a simple lookup table, or since they may not be allowed an algorithmic representation of one?

First: I don't run this contest. Therefore this are only suggestions. Raimo has the last word(s):
An algorithmic representation of a simple lookup table should be banned like the simple lookup table solution.
That's a general problem with beginners contests: You introduce restrictions to make it easier. But then the intended computation often becomes meaningless (since it always returns the same).
The possibility to pre-populate the board tries to make it more interesting (But since it makes only selections within the total of 92 solutions, the solution space remains fairly static).

But that gave me an idea:
How about raising the goal for those who think this contest is too easy: Make it n-queens instead of 8-queens.

Signature:
Code: Select all
`void solveboard_n(const std::vector<short int> &board, std::vector<std::vector<short int> > &solution, const int N = 8);`

Coordinate encoding:
Code: Select all
`// c is a value to be stored in std::vector<short int>x = c / N;y = c % N;c = x * N + y// (c >= 0 && c < N*N) == true;`

This would allow N >= 0 and N < 127.

There should be two evaluation groups:
8-queen and n-queen.
But for n==8 the solutions would be compatible and another evaluations of 8-queen against n-queen solutions should be fun.

Each contestant can only submit a n-queen or an 8-queen solutions.
IMHO the offical winner should be selected from the 8-queen solutions only (As was original intended, only changing the rules within a running contest is bad).
Therefore writing n-queen solutions is only for the fun (and the fame). And top-coders submitting a n-queen solution would give a newbie a chance to win this contest.

What do you think raimo?

jgbauman

Posts: 358
Joined: Sat Sep 27, 2003 9:00 am

I know the 8x8 board is small but that's the name of the problem. I could have created a contest with board of size 32x32 but 8x8 seemed more logical. Beginner contest is a beginner contest, though.
I promise the next contest will be a bit more intelligently planned.

jgbauman:

n-queen problem would be a good idea. I would be ready to judge it but I think it could be a problem to run two contests at the same time. How would we check who sends a solution to both contests and who doesn't? Ok, this isn't a problem if the n-queen contest is only for the fun but this is just a thought.
(The actual problem: Actually I'm just a bit lazy to judge two contests at the same time but maybe people understand why judging takes a bit longer then. )
jgbauman wrote:Therefore writing n-queen solutions is only for the fun (and the fame). And top-coders submitting a n-queen solution would give a newbie a chance to win this contest.

This is a good point. It's a great attempt to prevent top-coders from taking part in this contest.
Maybe this n-queen contest could be made "unofficial"? Another option would be to run it just after this beginner contest(and allow other pieces like knights and rooks). Or maybe the problem input would describe all the possible pieces and their movements etc.

EDIT: Btw, the beginner contest is also for the fun.

raimo

Posts: 372
Joined: Fri Sep 26, 2003 6:50 am
Location: Finland

An algorithmic representation of a simple lookup table should be banned like the simple lookup table solution.

Aren't they already banned in the contest rules? One cannot precompute the solutions beforehand nor even during the compilation and it is also forbidden to save any precomputed information between the runs of a function.

Dealing with formulas/algorithms constructing the solution is questionable but I would consider that they are forbidden too if they contain any kind of precomputed data. There isn't much precomputing in this problem but still it should be left out. I also think that the contests should be going to a direction where precomputing is useless(regardless of the contest rules) when the problems are solved.

raimo

Posts: 372
Joined: Fri Sep 26, 2003 6:50 am
Location: Finland

### -

Sorry if I ask this again, but you are allowed to use your own functions, right?

I looked at your function definition, and I didn't find it logical for me.

I would do it in a different way, am i allowed to do that?

Lisäksi, mukava nähdä täällä muita suomalaisia
Pauli

### Re: -

Pauli wrote:Sorry if I ask this again, but you are allowed to use your own functions, right?

Yes but you need to create the function as defined in the contest description. This is the function which is called in the evaluation code that measures the speed. The function is also expected to solve the problem.
I looked at your function definition, and I didn't find it logical for me.

It's not very logical but it's easy to evaluate plus it doesn't require any extra copying of std::vectors.

raimo

Posts: 372
Joined: Fri Sep 26, 2003 6:50 am
Location: Finland

Next