## 750 - 8 Queens Chess Problem

Moderator: Board moderators

frodo
New poster
Posts: 1
Joined: Fri Nov 23, 2001 2:00 am

### 750 - 8 Queens Chess Problem

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 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
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:
Did you see the blue checkmark ?

necropower
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am
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
New poster
Posts: 1
Joined: Sat May 11, 2002 7:55 am

### 750

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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
input of:
2 1

means row 2 column 1

Yuffie Choi
New poster
Posts: 3
Joined: Wed May 29, 2002 4:48 pm
Location: Hong Kong
Contact:
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.
Yuffie @.@

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
Again, have you handled the multiple input (i.e. the blue checkmark) properly?

necropower
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am
gimme an example , i didnt understand what u meant

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
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
New poster
Posts: 2
Joined: Mon Aug 19, 2002 8:27 am
Contact:

### What's wrong

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
New poster
Posts: 22
Joined: Thu Aug 01, 2002 10:26 am

### have a try!

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
New poster
Posts: 11
Joined: Fri Aug 23, 2002 9:42 pm
Location: MD, USA
Contact:
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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
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.
thanks

Code: Select all

``````cut it off because it's a soln after a few modifications
``````
[cpp][/cpp]
Last edited by anupam on Tue Mar 18, 2003 8:28 pm, edited 1 time in total.
"Everything should be made simple, but not always simpler"

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am