Page **1** of **1**

### 11085 - Back to the 8-Queens

Posted: **Mon May 21, 2007 9:01 pm**

by **DanS**

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

Posted: **Mon May 21, 2007 10:16 pm**

by **Robert Gerbicz**

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.

Posted: **Fri Jun 01, 2007 2:51 am**

by **DanS**

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?

### Re: 11085 - Back to the 8-Queens

Posted: **Sun May 13, 2012 5:12 am**

by **cyiucsy**

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.

### Re: 11085 - Back to the 8-Queens

Posted: **Wed Mar 04, 2015 1:50 pm**

by **xnorax**

I have used the same logic and it solved the sample above correctly but WA

1- save all possible solutions in 2D array

y[92][9]
2- compare input array

z[9]
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[9], TC, lineCounter,first,numm;
int y[92][9],z[9];
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;
}
```