11085 - Back to the 8-Queens

[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

[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.

[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?

[cyiucsy]

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]

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;
}