11085 - Back to the 8-Queens

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

DanS
New poster
Posts: 3
Joined: Mon May 21, 2007 8:55 pm

11085 - Back to the 8-Queens

I'm getting WA for this problem, but every test case that I came up with seemed to work fine. So I'm a bit stuck, as I don't see where the error is coming from.

for example:
1 7 4 6 8 2 5 3
Case 1: 0

1 7 2 6 3 5 8 4
Case 2: 1

1 1 1 1 1 1 1 1
Case 3: 7

1 2 3 4 5 6 7 8
Case 4: 7
Last edited by DanS on Fri Jun 01, 2007 2:51 am, edited 1 time in total.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
My accepted program gives

Code: Select all

Case 1: 0
Case 2: 2
Case 3: 7
Case 4: 7
So for the second case your program is wrong.

DanS
New poster
Posts: 3
Joined: Mon May 21, 2007 8:55 pm
OK, I'm now recursively searching for all 92 solutions and then determining the minimum number of moves by matching the board to each of these solutions. It still doesn't work.
Can I have a number of test cases & outputs to see where it's going wrong?

cyiucsy
New poster
Posts: 1
Joined: Sun May 13, 2012 5:06 am

Re: 11085 - Back to the 8-Queens

DanS wrote:OK, I'm now recursively searching for all 92 solutions and then determining the minimum number of moves by matching the board to each of these solutions. It still doesn't work.

Can I have a number of test cases & outputs to see where it's going wrong?
A rather late reply after 5 years.

Well I used a similar approach and I got AC-ed. I didn't even use any special test cases other than the sample I/O. So I am convinced that there's something wrong with your matching.

xnorax
New poster
Posts: 9
Joined: Thu Jun 26, 2014 9:31 pm

Re: 11085 - Back to the 8-Queens

I have used the same logic and it solved the sample above correctly but WA 1- save all possible solutions in 2D array y
2- compare input array z
3- output the minimum cost or number of moves

*NQueen function from Competitive programming book

Code: Select all

#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
int x, TC, lineCounter,first,numm;
int y,z;
long long int cost=0,mincost;
bool place(int queen, int row) {
for (int prev = 1; prev <= queen - 1; prev++) // check previously placed queens
if (x[prev] == row || (abs(x[prev] - row) == abs(prev - queen)))
return false; // an infeasible solution if share same row or same diagonal
return true;
}
void NQueens(int queen) {

for (int row = 1; row <= 8; row++)
if (place(queen, row)) { // if can place this queen at this row?
x[queen] = row; // put this queen in this row
if (queen == 8 ) {//solution is found
for (int c = 1; c<= 8; c++){//copy result
y[numm][c]=x[c];
}
numm++;
}
else
NQueens(queen + 1); // recursively try next position
} }

int main() {

int i, TCcounter;
numm=0;
NQueens(1); // generate all possible 8! candidate solutions
for (TCcounter=1; TCcounter<=1001; TCcounter++){

for (i=1; i<=8; i++) {
cin>>z[i];
}
first=0;

/*for (int n=0; n<92; n++) {//for each of 92 solutions
for (i=1; i<=8; i++) {
printf("y[%i][%i]= %i\n",n,i,y[n][i]);
}
printf("\n");
}*/

for (int n=0; n<92; n++) {//for each of 92 solutions
cost=0;
for (i=1; i<=8; i++) {
if(y[n][i]!=z[i])
cost++;
}
if (first==0) {
mincost=cost;
first++;
}
else if(cost<mincost){
mincost=cost;
}
}

printf("Case %i: %lld\n",TCcounter,mincost);

}//for TCcounter
return 0;
}