Possible Duplicate:
Dumb 8 Queens problem in C++
Hi I came over this question **
write an algorithm to print all ways of arranging 8 kings on the chess board so that none have same row,column ,diagonal
**
//initialize chess[i][j] to 0;
int king=100; //any other number except 0/1
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
//select any one position for the first column... lets start with j=0,i=0
if(chess[i][j]!=1)
chess[i][j]=king;
//now we should cross all rows with value i and column with value j
chess[i][]=1;
print(when chess[][]=king)
// we cannot enter king if chess[][]=1
}
}
how to check the diagonal part as well? also how to enumerate all the possible cases?
Thanks in adv..
To answer the specific question:
A diagonal move on the chessboard is always from (m,n) to (m+/-k, n+/-k); i.e. you move as many spaces horizontally as you do vertically. Therefore, to check if two queens, one on (i,j) and one on (p,q) are diagonally attacking each other, you check if abs(i-p) == abs(j-q).
To cross out all squares that can be diagonally attacked by a queen on (p,q), you need four loops of the form
for (i = p, j = q; i >= 0, j >= 0; i--, j--) { board[i][j] = 1 }
for (i = p, j = q; i >= 0, j < 8; i--, j++) { board[i][j] = 1 }
for (i = p, j = q; i < 8, j < 8; i++, j++) { board[i][j] = 1 }
for (i = p, j = q; i < 8, j >= 0; i++, j--) { board[i][j] = 1 }
that is, you walk all four arms of the x centred on your queen, crossing out squares till you hit the edge of the board.