0

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..

Community
  • 1
  • 1
garima
  • 5,154
  • 11
  • 46
  • 77
  • 6
    Amm, you mean queens. – ripper234 Mar 30 '11 at 13:27
  • 3
    I think you want the 8 queens problem. It is all explained in, of all places, wikipedia [8 Queens](http://en.wikipedia.org/wiki/Eight_queens_puzzle) – NealB Mar 30 '11 at 13:42
  • 1
    don't think this should have been closed - at least, from looking at the proposed duplicate, it covers a separate issue the answer to which is little help to this one. in general, a solution to the larger problem is only theoretically helpful when someone is stuck with a specific subproblem - the effort to read the larger answer and extract the small bit of information required may be beyond the poster. – Martin DeMello Mar 30 '11 at 15:19

1 Answers1

1

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.

Martin DeMello
  • 11,876
  • 7
  • 49
  • 64