750

frodo · Post by **frodo** » Fri Nov 23, 2001 6:38 am

hello there, I have a solution for the 8-queen problem (posted below) I belive it works just fine, but the judge says it doesn't solve the problem. I might be missing something... does anybody has a solution for this one? It would really help me out.

/* @JUDGE_ID: 1000AA 750 C++ "Backtracking" */
/*@BEGIN_OF_SOURCE_CODE*/
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

int columna[9];
int start_col; //la columna en que empece
int cont_sol; //contador de soluciones

int cumple(int col){
int k;
int cumplio;

k =1;
cumplio = 1;

for(int i=1;i<col;i++){ //repetir cuantas reinas ya tenga asignadas
if ((columna[col] == columna[k]) || (abs(columna[col]-columna[k]) == abs(col-k)))
cumplio=0;
k++;
}

if(col!=start_col)
if ((columna[col] == columna[start_col]) || (abs(columna[col]-columna[start_col]) == abs(col-start_col)))
cumplio=0;

return cumplio;
};

void reinas(int col){
if (cumple(col))
if (col==8){ //ya termine de hacer un recorrido
cont_sol++;
if(cont_sol<10)
cout<<" ";
cout<<cont_sol<<" ";
for(int k=1; k<=8; k++)
cout << columna[k]<<" ";
cout<<endl;
}
else
if(col+1==start_col)
reinas(col+1);
else
for (int j=1; j<=8; j++){
columna[col+1] = j;
reinas(col+1);
}
};

int main(){

int row,col;
int first_col;
cin>>row;
cin>>col;

columna[col]=row;
start_col=col;

cout<<"SOLN COLUMNn";
cout<<" # 1 2 3 4 5 6 7 8nn";

if(col==1)
first_col=2;
else
first_col=1;

for (int j=1; j<=8; j++){
columna[first_col] = j;
reinas(first_col);
}
return 0;
};
/*@END_OF_SOURCE_CODE*/

arnsfelt · Post by **arnsfelt** » Fri Nov 23, 2001 6:33 pm

Did you see the blue checkmark ?

necropower · Post by **necropower** » Tue Apr 23, 2002 4:36 pm

i have the same problem! but my code is different since i am using pure C

could u guys tell me a multi answer correct output?

like, my program generates this answer for:

1 1
2 2
3 3
4 4

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
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 2 7 3 6 8 5 1 4
2 4 7 3 8 2 5 1 6
3 7 1 3 8 6 4 2 5
4 7 5 3 1 6 8 2 4
SOLN COLUMN
# 1 2 3 4 5 6 7 8

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

is anything wrong with it?

[[]]'s Necropower

y94 · Post by **y94** » Sat May 11, 2002 7:59 am

what's wrong with my source?

-------------------------------
/* @JUDGE_ID: ??? 750 C++ "BackTracking" */

#include <stdio.h>
int Solution[8]={-1,-1,-1,-1,-1,-1,-1,-1};
int ColCheck[8];
int LeftCheck[15];
int RightCheck[15];
int Count;

void FindAll(int d)
{
if (d==8)
{
if (Count)
printf("\n");
printf("%2d ",++Count);
int i;
for (i=0; i<7; i++)
printf("%-2d",Solution[i]+1);
printf("%d",Solution[i]+1);
}
int i;
if (Solution[d]!=-1) FindAll(d+1);
else
for (i=0; i<8; i++)
{
if (!ColCheck[i] && !LeftCheck[d+i] && !RightCheck[d+7-i])
{
ColCheck[i]=1;
LeftCheck[d+i]=1;
RightCheck[d+7-i]=1;
Solution[d]=i;
FindAll(d+1);
ColCheck[i]=0;
LeftCheck[d+i]=0;
RightCheck[d+7-i]=0;
Solution[d]=-1;
}
}
}

void Process()
{
int a, b;
scanf("%d%d",&a, &b);
printf("SOLN COLUMN\n");
printf(" # 1 2 3 4 5 6 7 8\n\n");
a--;b--;
Solution[a]=b;
ColCheck[b]=1;
LeftCheck[a+b]=1;
RightCheck[a+7-b]=1;
Count=0;
FindAll(0);
Solution[a]=-1;
ColCheck[b]=0;
LeftCheck[a+b]=0;
RightCheck[a+7-b]=0;
}

void main()
{
int total;
int i;
scanf("%d",&total);
for(i=0;i<total;i++){
if (i) printf("\n\n");
Process();
}

}

----------------------------

Caesum · Post by **Caesum** » Sat May 11, 2002 11:07 am

input of:
2 1

means row 2 column 1

Yuffie Choi · Post by **Yuffie Choi** » Fri Jun 21, 2002 6:49 pm

Hey, I have compared ur output with mine (my program was accepted).
I can't find anything different with those input.
Maybe u can try other test cases to find out the bug.

10153EN · Post by **10153EN** » Fri Jun 21, 2002 7:39 pm

Again, have you handled the multiple input (i.e. the blue checkmark) properly?

necropower · Post by **necropower** » Fri Jun 21, 2002 10:20 pm

gimme an example , i didnt understand what u meant

10153EN · Post by **10153EN** » Sat Jun 22, 2002 7:20 am

What I mean is the blue tick symbol beside the problem number in the volume contents.

If you have not handled it, try http://acm.uva.es/problemset/minput.html

Terrible · Post by **Terrible** » Tue Aug 20, 2002 5:32 am

Code: Select all

#include <stdio.h>


void XXCross(short block[][8],short x, short y,short status){
	for (short z=0;z<=7;z++){
			block[z][y] = status;
			block[x][z] = status;
		if ((z+x)<=7 && (y+z)<=7)
			block[x+z][y+z] = status;
		if ((x-z)>=0 && (y-z)>=0 )
			block[x-z][y-z] = status;
		if ((x+z)<=7 && (y-z)>=0 )
			block[x+z][y-z] = status;
		if ((x-z)>=0 && (y+z)<=7 )
			block[x-z][y+z] = status;
	}
}


void backtrack(short block[][8],short x, short y,
			   short Num, short Result[], short& status, 
			   bool& valid,short tempx,short tempy,short& number){
	if (Num == 8|| !valid ){
		if (Num ==8){
			number++;
			printf(" %d ",number);
			for (short m=0;m<=7;m++){
				printf("%d ",Result[m]);
		
				
				 
			}
			printf("\n");
			
		}
	}else{
		
		valid= false;


		for(short i=y;i<=7;i++){
			for (short j=x;j<=7;j++)
				if (block[j][i] != status){
					Result[i] = j+1;
					Num++;
					XXCross(block, j, i,status);
					
					x=j;
					y=i;
					valid = true;
					break;
				}
				if (valid){
					tempx =x;
					tempy =y;
					y++;
					x=0;
					
					break;
				}
				if (i==7 && !valid){
					x=7;
					y=7;
				}
		}
	

	
		backtrack(block,x,y,Num,Result,
			status,valid,tempx,tempy,number);
		
		if (x==7 &&y ==7 && !valid)
			valid = false;
		else
			valid = true;
		x= tempx;
		y= tempy;
		Result[y] = 0;
		
		status++;
		
		for (short p=0;p<=7;p++)
			if (Result[p]!=0){
				XXCross(block, Result[p]-1, p,status);
			}
		Num--;

		x++;
		if (x >7){
			x=0;
			y++;
	
		}
		if (y!=8 && !(x==7&&y==7))
			backtrack(block,x,y,Num,Result,
			status,valid,tempx,tempy,number);
		

	}
}


void main()
{
	short x,y;
	short block[8][8];

	short Result[8];
	short Num =0;
	short status;
	bool valid = true;
	short number=0;
	short PP=0;
	scanf("%d",&PP);
	printf("\n");
	while (PP--!=0){

		scanf("%d %d",&x,&y);
		status=0;
		Num=0;
		valid = true;
		number=0;
		for (short	q=0; q<= 7;q++){
		
			for (short w=0;w<=7 ;w++){
			
				block[q][w]=0;
			}
			Result[q] =0;
		}
		
		block[x-1][y-1] =-1;
		status++;
		XXCross(block, x-1, y-1,status);
		Result[y-1] = x;
		Num++;
		printf("SOLN COLUMN\n"); 
		printf(" # 1 2 3 4 5 6 7 8\n\n");
		
		backtrack(block,0,0,Num,Result,
			status,valid,0,0,number);
		printf("\n");

	}
	
}

why run time error?
Should anyone help me?

liusu · Post by **liusu** » Thu Aug 22, 2002 6:45 am

give you some example input and output,have a try:
[pascal]3
1 3
SOLN COLUMN
# 1 2 3 4 5 6 7 8

1 2 6 1 7 4 8 3 5
2 4 6 1 5 2 8 3 7
3 4 7 1 8 5 2 6 3
4 4 8 1 3 6 2 7 5
5 4 8 1 5 7 2 6 3
6 5 3 1 6 8 2 4 7
7 5 3 1 7 2 8 6 4
8 5 7 1 3 8 6 4 2
9 5 7 1 4 2 8 6 3
10 6 3 1 7 5 8 2 4
11 6 3 1 8 4 2 7 5
12 6 3 1 8 5 2 4 7
13 6 4 1 5 8 2 7 3
14 7 3 1 6 8 5 2 4
15 8 3 1 6 2 5 7 4
16 8 4 1 3 6 2 7 5
2 4
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
7 6
SOLN COLUMN
# 1 2 3 4 5 6 7 8

1 1 5 8 6 3 7 2 4
2 3 5 2 8 1 7 4 6
3 3 5 8 4 1 7 2 6
4 3 6 8 1 4 7 5 2
5 3 6 8 1 5 7 2 4
6 4 1 5 8 2 7 3 6
7 4 6 8 3 1 7 5 2
8 4 8 5 3 1 7 2 6
9 5 1 8 4 2 7 3 6
10 5 1 8 6 3 7 2 4
11 5 2 8 1 4 7 3 6
12 6 4 2 8 5 7 1 3
13 6 8 2 4 1 7 5 3
14 8 2 5 3 1 7 4 6[/pascal]

Good luck!

mmammel · Post by **mmammel** » Sun Sep 15, 2002 4:39 pm

I am sure my program produces the correct answer -- it finds all 92 possible solutions if no queen is initially placed. I don't think I have mixed up ROW and COL, and I even submitted a version with them switched to make sure. But I get WA -- is there something tricky with output format? I assume that for N>9 you drop the leading space so it lines up. Example:

Code: Select all

2 3
SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

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

What's wrong with this??
Thanks,
Mark

PS sorry but the space in front of N=1 thru 9 doesn't show up here...if I add another it shifts it TWO spaces!

anupam · Post by **anupam** » Fri Jan 10, 2003 1:08 pm

hello best boyz and girls, i think my algorithm is right and i used dp to solve the problem. but i am getting wa for a long time.
will any 1 check it?
their may be fault in output format.
please help.
thanks

Code: Select all

cut it off because it's a soln after a few modifications

[cpp][/cpp]
please help..[/b]

Subeen · Post by **Subeen** » Tue Mar 18, 2003 6:48 pm

i used backtracking but got WA. cann't find the bug. help me plz.

( i removed the code after finding bug... if someone need help about this than let me know...

anupam · Post by **anupam** » Tue Mar 18, 2003 8:34 pm

it's nothing but a problem of printing the first col 1 2 3 4 5 6 7 8..
try several tims changing it and then get ac..

OJ Board

750 - 8 Queens Chess Problem

750 - 8 Queens Chess Problem

What's wrong

have a try!