750 - 8 Queens Chess Problem

[efr_shovo]

750 gives W.A. Please give me someCritical Input & Output

[dumb dan]

note that it is a multiple input problem...

input:

Code: Select all

4
1 2
6 7
7 8
8 8

output:

Code: Select all

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

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

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

 1      1 7 5 8 2 4 6 3
 2      2 5 7 1 3 8 6 4
 3      2 5 7 4 1 8 6 3
 4      2 7 5 8 1 4 6 3
 5      4 2 7 5 1 8 6 3
 6      4 7 1 8 5 2 6 3
 7      4 8 1 5 7 2 6 3
 8      5 2 4 7 3 8 6 1
 9      5 3 1 7 2 8 6 4
10      5 3 8 4 7 1 6 2
11      5 7 1 4 2 8 6 3
12      5 7 4 1 3 8 6 2
13      5 8 4 1 7 2 6 3
14      7 3 8 2 5 1 6 4

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

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

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

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

[_.B._]

Greetings!
Pretty useful post dumb dan

Keep posting!

[Tanu]

Hi Solvers I wanna solve the problem 750 but its telling wrong answer...
Would U help me By checking my code output...
I'll also glad to have any advice(in board or private massage) for learning backtracking...

Code: Select all

#include<stdio.h>
#include<math.h>
int count;
int x[8];
int P,Q;
bool Place(int k,int i)

{
	int j;
	for(j=1;j<=k-1;j++)
	{
		if((x[j]==i)||(abs(x[j]-i))==(abs(j-k)))
			return false;
	}
	return true;
}

void NQueens(int k,int n)

{
	int i,j;
	for(i=1;i<=n;i++)
	{
		if(Place(k,i))
		{
			x[k]=i;
			if(k==n&&x[Q]==P)
			{
			
				count++;
				printf("%2d     ",count);
				for(j=1;j<=n;j++)
					printf("%2d",x[j]);
				printf("\n");
			}
			else
				NQueens(k+1,n);
		}
	}
}
main()
{
	
	bool tag=0;
	long test,testcase;
	scanf("%ld",&testcase);
	for(test=1;test<=testcase;test++)
	{
		scanf("%d%d",&P,&Q);

		if(tag==0)
			tag=1;
		else
			printf("\n");
		
		printf("SOLN       COLUMN\n");
		printf(" #      1 2 3 4 5 6 7 8\n\n");
		count=0;
		NQueens(1,8);
	}
}

[Jan]

Hi Tanu,
May be your backtracking is wrong. There are 92 solutions. You can pre-calculate and save them, and finally print according to the input given.

Now your code fails to return the output for the following set..

Input:

Code: Select all

2

2 2

2 4

Output:

Code: Select all

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

 1      4 2 5 8 6 1 3 7
 2      4 2 7 3 6 8 1 5
 3      4 2 7 3 6 8 5 1
 4      4 2 7 5 1 8 6 3
 5      4 2 8 5 7 1 3 6
 6      4 2 8 6 1 3 5 7
 7      5 2 4 6 8 3 1 7
 8      5 2 4 7 3 8 6 1
 9      5 2 6 1 7 4 8 3
10      5 2 8 1 4 7 3 6
11      6 2 7 1 3 5 8 4
12      6 2 7 1 4 8 5 3
13      7 2 4 1 8 5 3 6
14      7 2 6 3 1 4 8 5
15      8 2 4 1 7 5 3 6
16      8 2 5 3 1 7 4 6

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

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

Hope it works. Good luck.

[sunny]

some 1 pls explain me why WA. my output was correct for all test cases i found so far.



#include<stdio.h>
#include<math.h>
int board[10][10],colstat[10],ldiag[20],rdiag[20];
int nway,res[10],row,col;
void search(int r)
{
int c,m,n;
if(r==9) {
for(m=1;m<=8;m++) {
if(m==col && res[m]==row) {
nway++;
if(nway/10==0) printf(" %d ",nway);
else printf(" %d ",nway);
for(n=1;n<=8;n++) printf(" %d",res[n]);
printf("\n");

break;
}
}

return ;
}

for(c=1;c<=8;c++){
if(board[r][c]==0 && colstat[c]==0 && ldiag[r+c]==0 && rdiag[r-c+8]==0 )
{

board[r][c]=1;
colstat[c]=1;
ldiag[r+c]=1;rdiag[r-c+8]=1;
res[r]=c;

search(r+1);

board[r][c]=0;
colstat[c]=0;
ldiag[r+c]=0;rdiag[r-c+8]=0;
}

}
return ;
}


int main()
{

int i,j,k;


while(scanf("%d %d",&row,&col)!=EOF){
if(row>8 || col>8) continue;
printf("SOLN COLUMN\n");
printf(" # 1 2 3 4 5 6 7 8\n\n");


for(i=1;i<=8;i++) for(j=1;j<=8;j++) {board[j]=0;
colstat=0;}
for(i=1;i<=20;i++) {ldiag=0;rdiag=0;}
nway=0;
search(1);





}

return 0;


}

[smilitude]

Sunny,
I had the same problem too.
Look at the updated problem statement.... they have some kind of

<total input num>
<row > <column>

style right now!

[snar]

Simple implementation of 8 Queens Problem. But why WA?

Code: Select all

// 750 8 Queens Chess Problem 

#include <stdio.h>
#include <stdlib.h>
#define N 8 // the N x N board

int d[N+1],c,r,count;

bool ispossible(int col, int row) {	
	int i;
	if (row==r || abs(row-r)==abs(col-c)) return false;
	for (i=1; i<col; i++)
		if (row==d[i] || abs(row-d[i])==abs(col-i)) return false;
	return true;
}
void step(int n) {
	int i;
	if (n == N+1) {
		printf(" %d     ", ++count);
		for (i=1; i<=N; i++)
			printf(" %d", d[i]);
		putchar('\n');
		return;
	}			
	if (n == c)
		step(n+1);
	else
		for (i=1 ; i<=N ; i++)
			if (ispossible(n,i)) {
				d[n] = i;
				step(n+1);
			}	
}
void main() {
	int i;
    scanf("%d %d", &r, &c);
	d[c] = r;
	printf("SOLN       COLUMN\n #      1 2 3 4 5 6 7 8\n\n");
	count = 0;
	step(1);
}

[mf]

It's a multiple input problem.

If you have an old version of problem statement, check the new one here http://acm.uva.es/p/v7/750.html

[snar]

mf, thanks indeed

[ferrizzi]

why I got PE? could someone give me some tricky input?

for the input:

Code: Select all

4

1 2
6 7
7 8
8 8

i got the output:

Code: Select all

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

 1      4 2 5 8 6 1 3 7
 2      4 2 7 3 6 8 1 5
 3      4 2 7 3 6 8 5 1
 4      4 2 7 5 1 8 6 3
 5      4 2 8 5 7 1 3 6
 6      4 2 8 6 1 3 5 7
 7      5 2 4 6 8 3 1 7
 8      5 2 4 7 3 8 6 1
 9      5 2 6 1 7 4 8 3
10      5 2 8 1 4 7 3 6
11      6 2 7 1 3 5 8 4
12      6 2 7 1 4 8 5 3
13      7 2 4 1 8 5 3 6
14      7 2 6 3 1 4 8 5
15      8 2 4 1 7 5 3 6
16      8 2 5 3 1 7 4 6

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

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

I would like to know where are the mistake?

[tonmoycse05]

#include<stdio.h>
#include<math.h>

long int place(long int,long int);

void queen(long int);

long int p[8],r,c,count;

void main(void)
{
while(2==scanf("%ld %ld",&c,&r))
{
printf("SOLN COLUMN\n");
printf(" # 1 2 3 4 5 6 7 8\n\n");
count=0;
queen(0);
}
}

long int place(long int k,long int i)
{
long int j;
for(j=0;j<k;j++)
{
if((p[j]==i)||(abs(p[j]-i)==abs(j-k)))
{
return 0;
}
}
return 1;
}

void queen(long int k)
{
long int i,j;
for(i=0;i<8;i++)
{
if(place(k,i)==1)
{
p[k]=i;
if(k==7)
{
if(p[r-1]==c-1)
{
count++;
printf(" %ld ",count);
for(j=0;j<8;j++)
{
printf ("%ld ",p[j]+1);
}
printf("\n");
}
}
else
queen(k+1);
}
}
}

[Jan]

Search your problem first. If you find a thread then try to use it. Dont open a new one unless there is none. Check this thread
http://online-judge.uva.es/board/viewto ... hlight=750
Hope it helps.

[l314]

Why my code just got P.E.?
plz help me to get AC, thx.

code is killed.

[helloneo]

Edited