750 - 8 Queens Chess Problem
Moderator: Board moderators
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 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*/
/* @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*/
-
- 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
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
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();
}
}
----------------------------
-------------------------------
/* @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();
}
}
----------------------------
-
- New poster
- Posts: 3
- Joined: Wed May 29, 2002 4:48 pm
- Location: Hong Kong
- Contact:
-
- New poster
- Posts: 20
- Joined: Wed Dec 26, 2001 2:00 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
If you have not handled it, try http://acm.uva.es/problemset/minput.html
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");
}
}
Should anyone help me?
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!
[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!
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:
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!
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
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!
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
[cpp][/cpp]
please help..[/b]
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
please help..[/b]
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"
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...
( i removed the code after finding bug... if someone need help about this than let me know...
Last edited by Subeen on Wed Mar 19, 2003 7:08 pm, edited 1 time in total.