Chess Queens on NxM board

[Badshah]

Hi all..i have been trying on chess problems..the most faous one would be the 8 queens..
i Just found this one and am mind blocked on the algo : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2533

[hamsterman]

This one is a lot more simple than 8 queens. The algorithm is - for each tile in your grid, if a black queen stood there, count how many placements of a white queen would threaten it. Then add it all up. What you really need to do is, given a tile, find the lengths of the column, row and diagonals that go through it (excluding the tile itself).

[Badshah]

yeah, i know it must be simpler ..
although i din get ur algo, for itx not NxN board it can be any width n lenth as u see in sample,for example 100 x 223=10907100 ?

[hamsterman]

Consider a 5 x 6 grid with a black queen on a tile (1, 1)

* * *   X   
* Q * * * *
* * *   X   
  *   *   X
X * X   *   

(X are just black tiles - I hoped they would improve readability). If a white queen was placed on any of *s, they would be able to capture each other. Thus you need to count all *s. Obviously the *s are placed on the same row, column and diagonals as Q. It's quite trivial to count..

[Badshah]

yea..dats like if we assume the position but what would be the answer to 5 x 6 grid..like we dont know which tile queen would be on ? :S

[hamsterman]

The number you're looking for is the sum of *s for all possible positions.

[Badshah]

how woul we know the possible positions on 100 x 223?

[hamsterman]

int width = 223, height = 100;
for(int i = 0; i < width; i++){
   for(int j = 0; j < height; j++){
      //count *s if the Q was on tile (i, j)
   }
}