I have an N by N grid and K queens in it. The queen can move vertically, horizontally or diagonally. I want to figure out if any queen can attack any other queen in O(N) time.
Use the same technique as in the last answer for rook problem, just add arrays for diagonals. DiagUpRight[2*N-1] and DiagUpLeft[2*N-1].
Q(x,y) marks diagonals DiagUpLeft[x + y] and DiagUpRight[N-1 - y + x]