167 - The Sultan's Successors

Moderator: Board moderators

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

167 - The Sultan's Successors

Why does this code get WA? I just use formula to get the 8 positions and rotate the board in 4 directions to get the max sum. Where are the bugs?
[c]
#include<stdio.h>
void main(void)
{
int board[8][8],k,x,y,z,ans[4],max;
scanf("%d",&k);
for(x=0;x<k;x++)
{
for(y=0;y<8;y++)
for(z=0;z<8;z++)
scanf("%d",&board[y][z]);
ans[0]=board[0][5]+board[1][0]+board[2][4]+board[3][1]+board[4][7]+board[5][2]+board[6][6]+board[7][3];
ans[1]=board[0][6]+board[1][4]+board[2][2]+board[3][0]+board[4][5]+board[5][7]+board[6][1]+board[7][3];
ans[2]=board[0][4]+board[1][1]+board[2][5]+board[3][0]+board[4][6]+board[5][3]+board[6][7]+board[7][2];
ans[3]=board[0][4]+board[1][6]+board[2][0]+board[3][2]+board[4][7]+board[5][5]+board[6][3]+board[7][1];
for(y=0,max=0;y<4;y++)
if(ans[y]>max)
max=ans[y];
printf("%5d\n",max);
}
}
[/c]

visser
New poster
Posts: 8
Joined: Mon Jun 10, 2002 11:13 am
Location: Netherlands
There are a bit more solutions than 4 for the 8-queen problem.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
[c]
#include<stdio.h>
void main(void)
{
int board[8][8],k,x,y,z,ans[8],max;
scanf("%d",&k);
for(x=0;x<k;x++)
{
for(y=0;y<8;y++)
for(z=0;z<8;z++)
scanf("%d",&board[y][z]);
ans[0]=board[0][5]+board[1][0]+board[2][4]+board[3][1]+board[4][7]+board[5][2]+board[6][6]+board[7][3];
ans[1]=board[0][6]+board[1][4]+board[2][2]+board[3][0]+board[4][5]+board[5][7]+board[6][1]+board[7][3];
ans[2]=board[0][4]+board[1][1]+board[2][5]+board[3][0]+board[4][6]+board[5][3]+board[6][7]+board[7][2];
ans[3]=board[0][4]+board[1][6]+board[2][0]+board[3][2]+board[4][7]+board[5][5]+board[6][3]+board[7][1];
ans[4]=board[0][2]+board[1][7]+board[2][3]+board[3][6]+board[4][0]+board[5][5]+board[6][1]+board[7][4];
ans[5]=board[0][3]+board[1][1]+board[2][7]+board[3][5]+board[4][0]+board[5][2]+board[6][4]+board[7][6];
ans[6]=board[0][3]+board[1][6]+board[2][2]+board[3][7]+board[4][1]+board[5][4]+board[6][0]+board[7][5];
ans[7]=board[0][1]+board[1][3]+board[2][5]+board[3][7]+board[4][2]+board[5][0]+board[6][6]+board[7][4];
for(y=0,max=0;y<8;y++)
if(ans[y]>max)
max=ans[y];
printf("%5d\n",max);
}
}
[/c]

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
Do some research. There are quite a bit more solutions to the 8queen

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
I found 12 fundamental solutions. Then I rotate one of them in 4 directions and turn over to rotate it in 4 directions again. Then I got 8*12=96 solutions. Am I right?

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

close, but no sigar

You're allmost there
Some of the fundamental solutions will have symmetry, so they will remain unchanged after rotation or reflection. The actual number is...

[SPOILER] XCII [/SPOILER]

Happy hunting,
-xenon

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
So I have to calculate the solutions instead of list all of them?

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
Well, I think it is for you to decide how you implement the problem.
Basically, anything is alowed as long as it gives the correct answer in the correct format within 30 seconds

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:
I have a question.
I try to solve this problem using general backtracking algorithm.
So I get 22 solution.
But what is the difference between general 8 - queen solution and this problem's solution?
Only pivoting and rotating my 8 - queen solution is this problem's answer?
If it is true, then why general 8 - queen solution can't catch all possible
case? ( Xenon said that there are total 92 solutions )
My program is wrong or other explaination is exist?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
If I correct remember, after rotating and mirroring all solutions generating from backtrack we have 192 possible solutions ...
Maybe this help us

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:
Oh... I'm sorry. My program was wrong.
In the classic n - queens problem, 8*8 chess board has 92 solutions.
( From the description of problem 10401. )

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Sorry, (
I check my program(Acc) and I saw that I use only 92 solutions for 8-queen problem ....
That must be other problem with your code ...

After generating all possibilities you have only to find maximum sum of fields, in which queen are placed .... maybe your search algorithm isn't good ?

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:
At last, I accepted my code.
It's only my mistake using backtracking algorithm.
Using general N - Queen algorithm, this problem can solve easily.

Pavl0
New poster
Posts: 16
Joined: Sun Apr 18, 2004 2:57 pm
my prog find all 92 positions at start prog end use it far all cases
J get AC
J use iterratin methot for nqp for 8 is fast

Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:

HINT FOR 167 [Sultan's Successor]

There will be 92 non-attacking combinations.

You will have to use Backtracking to find them all.

Hope it helps !!