750 - 8 Queens Chess Problem

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

Moderator: Board moderators

jupiter777
New poster
Posts: 8
Joined: Sun Mar 30, 2003 9:44 pm
Location: bangladesh

help!p:-750

Post by jupiter777 » Sun Mar 30, 2003 9:57 pm

i can't find out whats the wrong with my code! plz help me with that.
here's my code:-
.............................................................................................................
#include<stdio.h>
#include<math.h>
int x[100],a=0,b,rec[1000][10];
int place(int k, int i){
int j;
for(j=1;j<k;j++)
if((x[j]==i)||(labs(x[j]-i)==labs(j-k)))
return 0;
return 1;
}
void nqueens(int k, int n){
int i;
for(i=1;i<=n;i++){
if(place(k,i)){
x[k]=i;
if(k==n){ b=0;
for(i=1;i<=n;i++){
rec[a]=x;
b++;
}
a++;
}
else nqueens(k+1,n);
}
}
}
int main(){
// freopen("nQu.in","rt",stdin);
// freopen("nquee.out","w",stdout);
int k,n,i,r,c,j,gg,p[9],y,v;
nqueens(1,8);
while(scanf("%d%d",&r,&c)==2){
y=1;
printf("SOLN\t COLUMN\n");
printf(" #\t");
for(gg=1;gg<=8;gg++){
if(gg>1)printf(" ");
printf("%d",gg);
}
printf("\n\n");

for(i=0;i<a;i++) {
gg=0;
if(rec[r-1]==c){
printf(" %d\t",y);
y++;
for(j=0;j<b;j++){

if(gg>0) printf(" ");

printf("%d",rec[j]);
gg++; }
printf("\n");
}
}
}

return 0;
}

jupiter777
New poster
Posts: 8
Joined: Sun Mar 30, 2003 9:44 pm
Location: bangladesh

750

Post by jupiter777 » Mon Mar 31, 2003 10:05 am

i can't find out whats the wrong with my code! plz help me with that.
here's my code:-
.............................................................................................................
#include<stdio.h>
#include<math.h>
int x[100],a=0,b,rec[1000][10];
int place(int k, int i){
int j;
for(j=1;j<k;j++)
if((x[j]==i)||(labs(x[j]-i)==labs(j-k)))
return 0;
return 1;
}
void nqueens(int k, int n){
int i;
for(i=1;i<=n;i++){
if(place(k,i)){
x[k]=i;
if(k==n){ b=0;
for(i=1;i<=n;i++){
rec[a]=x;
b++;
}
a++;
}
else nqueens(k+1,n);
}
}
}
int main(){
// freopen("nQu.in","rt",stdin);
// freopen("nquee.out","w",stdout);
int k,n,i,r,c,j,gg,p[9],y,v;
nqueens(1,;
while(scanf("%d%d",&r,&c)==2){
y=1;
printf("SOLN\t COLUMN\n");
printf(" #\t");
for(gg=1;gg<=8;gg++){
if(gg>1)printf(" ");
printf("%d",gg);
}
printf("\n\n");

for(i=0;i<a;i++) {
gg=0;
if(rec[r-1]==c){
printf(" %d\t",y);
y++;
for(j=0;j<b;j++){

if(gg>0) printf(" ");

printf("%d",rec[j]);
gg++; }
printf("\n");
}
}
}

return 0;
}

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Tue Apr 01, 2003 3:31 pm

using spaces instead of tab ('\t') might help

kh9
New poster
Posts: 4
Joined: Fri Jun 06, 2003 11:29 pm

Post by kh9 » Fri Jun 06, 2003 11:40 pm

I keep getting rejected, and the problem seems to be input:
I 've tried
cin>>R>>C;

and

scanf("%d%d", &R,&C);

but I keep getting 20 for R (i found this out using assert()), which doesn't make sense...

did you guys use any special tricks for input? Or is the input just wrong?
any help is appreciated.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sat Jun 07, 2003 3:33 pm

no tsure ofg your problem.
but in my case it was because of printing the heading only.
try combinations of the heading.
--
anupam :oops: :oops: always pessimistic
"Everything should be made simple, but not always simpler"

kh9
New poster
Posts: 4
Joined: Fri Jun 06, 2003 11:29 pm

Post by kh9 » Fri Jun 13, 2003 12:11 pm

Still I'm running into problems with input. I even tried this simple code:
[c]
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

int main ()
{

int row;
int col;

if (scanf ("%d %d", &row, &col)!=2){
return 1;
}
if (row<1 || row>8 || col<1 ||col>8 ){
if (row==20){
assert(0);
}
}

return 0;
}


[/c]

And it gets Runtime Error, proving that it indeed reads 20 for row number.
I'm really confused now...
Does anyone have any idea why this happens?

-----------------------
ok, i've figured it out, it's "multiple input" format. It would be more helpful
to state the format inside the problem statement though. The sample input is especially misleading.

Dejarik
New poster
Posts: 32
Joined: Sun Mar 07, 2004 1:23 pm
Location: Barcelona, SPAIN
Contact:

Wrong judgement in 750?

Post by Dejarik » Sun Mar 21, 2004 10:50 pm

I've made some tests with the Online Judge for the problem 750 - "8 Queens Chess Problem" and i might supose that something is wrong in the inputs used for the judge to eval the problem.

The problem specifies Input to your program will be two numbers separated by a blank. The numbers represent the square on which one of the eight queens must be positioned. A valid square will be represented; it will not be necessary to validate the input.

And after study all the wrong answers i received from judge i reached the conclusion that one of the inputs has number 20 as one of the two numbers that forms the input line. The number 20 cannot be a valid number, only 1 to 8 should be allowed, so the executions always get wrong answer in this problem.

This is not a very difficult problem, but its rating is ridiculous (less than 10%), that's another fact that makes me believe something is not working in the jugdement...

Am I wrong? Or really the input is corrupted? I don't know if I must post this topic in this section or send a mail to any administrator of the Online Judge...

I will be waiting an answer, thank you very much!

Joan, SPAIN

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs » Sun Mar 21, 2004 11:54 pm

Well, it's a multiple input problem... :wink: Probably, 20 is the number of test cases.

PS: For the description of multiple input format take a look here.

Good luck! :)

Dejarik
New poster
Posts: 32
Joined: Sun Mar 07, 2004 1:23 pm
Location: Barcelona, SPAIN
Contact:

Post by Dejarik » Mon Mar 22, 2004 12:20 am

But in this problem it is not specified that a multiple input should be considered. It specifies that only two numbers are the input of the problem.

http://acm.uva.es/p/v7/750.html

Did you solve it allowing multiple input? Thanks!

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs » Mon Mar 22, 2004 12:54 am

There's a blue tick next to the problem's name on this page. It means multiple input.

I'll copy-paste the meanings of the colours:
The yellow colour means a special correction program for that problem; the blue colour means multiple input; finally, the green colour (a mix of blue and yellow) means a problem with multiple inputs and a special judge program.
Good luck! :)

Dejarik
New poster
Posts: 32
Joined: Sun Mar 07, 2004 1:23 pm
Location: Barcelona, SPAIN
Contact:

Post by Dejarik » Mon Mar 22, 2004 10:43 pm

You were right! Thank you very much for you help! I thought that all the problems with multiple input would be explained in the statement of each problem. Now I will check the color of the mark before implementing my solutions...

THanks again!

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

750

Post by dpitts » Wed Mar 24, 2004 12:30 pm

My code works for sample, but gets WA. I'm aware its multiple-input, and have coded for such.

[cpp]/*code removed*/[/cpp]

Any test cases would be appreciated. Thanks.
Last edited by dpitts on Wed Mar 24, 2004 9:17 pm, edited 1 time in total.

Dejarik
New poster
Posts: 32
Joined: Sun Mar 07, 2004 1:23 pm
Location: Barcelona, SPAIN
Contact:

Post by Dejarik » Wed Mar 24, 2004 12:46 pm

I solved this problem a few days ago. If you post some inputs and outputs of your executions, i will do the same with my file to check where might be the wrong answer...

Joan, SPAIN

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

Post by dpitts » Wed Mar 24, 2004 9:18 pm

I found my problem.
I got column/row mixed up in the input.
I have AC now.

orojas
New poster
Posts: 5
Joined: Tue Jul 20, 2004 6:44 pm

750 something wrong in my code?

Post by orojas » Thu Jul 22, 2004 5:47 am

I can't figure out what's wrong with my program:

on the input:

1
1 1

Note the first number is the number of cases(since is a multiple input problem as stated in the problemset)

i yields:

SOLN COLUMN
# 1 2 3 4 5 6 7 8

1 1 5 8 6 3 7 1 4 /*Here is the problem*/
2 1 6 8 3 7 4 2 5
3 1 7 4 6 8 2 5 3
4 1 7 5 8 2 4 6 3

when it should be:

SOLN COLUMN
# 1 2 3 4 5 6 7 8

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

even though when i print the board(//printBoard()//) to check it's correct
i can see the mistake
i would apreciate any help!!!

Here is my code:

[c]#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int colum[8];
} SOLUCION;

SOLUCION sols[100];/*Array of sols*/

char board[8][8]; /*board*/
int nSols; /*Number of solutions*/

void printBoard() {
int i,j;
system("cls");
for(i=0;i<8;i++) {
for(j=0;j<8;j++) {
printf("%d ",board[j]);
}
printf("\n");
}
system("pause");

}

int compara(const void *a,const void *b) { /*func used in qsort*/
SOLUCION S1,S2;
int i;
S1 = *(SOLUCION *)a;
S2 = *(SOLUCION *)b;
for(i=0;i<8 && S1.colum==S2.colum;i++);
if(i==8) {
return 0;
}
else {
return(S1.colum-S2.colum);
}
}
/*To validate queens positon*/
int valid(int y,int x) {
int i,j;
int res=1;
/*VERTICAL*/
for(i=y;i>-1;i--) {
if(board[x]==1) {
res=0;
break;
}
}
for(i=y;i<8;i++) {
if(board[x]==1) {
res=0;
break;
}
}
/*DIAGONAL*/
for(i=y,j=x;i>-1 && j>-1;i--,j--) {
if(board[j]==1) {
res=0;
break;
}
}
for(i=y,j=x;i>-1 && j<8;i--,j++) {
if(board[j]==1) {
res=0;
break;
}
}
/**/
for(i=y,j=x;i<8 && j>-1;i++,j--) {
if(board[j]==1) {
res=0;
break;
}
}
for(i=y,j=x;i<8 && j<8;i++,j++) {
if(board[i][j]==1) {
res=0;
break;
}
}
return res;
}

/*SOLVER FUNCTION*/
void solve(int step,int row,int col) {
int i,k;
if(step==8) {
nSols++;
/*printBoard();*/
}
else {
if(step==row) {
sols[nSols].colum[col]=row;
solve(step+1,row,col);
}
else {
for(k=0;k<8;k++) {
if(valid(step,k)==1) {
board[step][k]=1;
sols[nSols].colum[k]=step;
solve(step+1,row,col);
board[step][k]=0;
}
}
}
}
}
/*END OF SOLVER*/

int main() {
int row,col;
int ncasos;
int i,j;

/* FILE *in;
in=fopen("8queens.in","r");*/
scanf("%d",&ncasos);
while(ncasos>0) {
ncasos--;
scanf("%d %d",&row,&col);
nSols=0;
memset(board,0,sizeof(int)*64);
memset(sols,0,sizeof(SOLUCION)*100);
printf("SOLN\t COLUMN\n");
printf(" #\t");
for(i=0;i<8;i++) {
printf("%d ",i+1);
}
printf("\n\n");
board[row-1][col-1]=1;
solve(0,row-1,col-1);
qsort(sols,nSols,sizeof(SOLUCION),compara);
for(i=0;i<nSols;i++) {
printf("%2d\t",i+1);
for(j=0;j<8;j++) {
printf("%d ",sols[i].colum[j]+1);
}
printf("\n");
}
printf("\n");
}
// fclose(in);
system("pause");
return 0;

}[/c]

Post Reply

Return to “Volume 7 (700-799)”