167 - The Sultan's Successors

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

167 - The Sultan's Successors

Post by htl »

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

Post by visser »

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

Post by htl »

How about this code? It still get WA.
[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

Post by xenon »

Do some research. There are quite a bit more solutions to the 8queen :lol:

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

Post by htl »

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

Post by xenon »

You're allmost there :P
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

Post by htl »

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

Post by xenon »

Well, I think it is for you to decide how you implement the problem. :wink:
Basically, anything is alowed as long as it gives the correct answer in the correct format within 30 seconds :P

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Post by soyoja »

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?
I'm so confused... Anyone tell me about this question.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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:

Post by soyoja »

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. )
Now I rewrite my source code.... thanks your kindly answer.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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:

Post by soyoja »

At last, I accepted my code.
It's only my mistake using backtracking algorithm.
Using general N - Queen algorithm, this problem can solve easily.
Thanks for your advise.

Pavl0
New poster
Posts: 16
Joined: Sun Apr 18, 2004 2:57 pm

Post by Pavl0 »

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 :)

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

HINT FOR 167 [Sultan's Successor]

Post by Ali Arman Tamal »

There will be 92 non-attacking combinations. :wink:

You will have to use Backtracking to find them all.


Hope it helps !! :)

Post Reply

Return to “Volume 1 (100-199)”