167 - The Sultan's Successors

[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]

There are a bit more solutions than 4 for the 8-queen problem.

[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]

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

[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]

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]

So I have to calculate the solutions instead of list all of them?

[xenon]

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]

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]

If I correct remember, after rotating and mirroring all solutions generating from backtrack we have 192 possible solutions ...
Maybe this help us

DM

[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]

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

[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]

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]

There will be 92 non-attacking combinations.

You will have to use Backtracking to find them all.


Hope it helps !!