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