Checkers algorithm - find the best last move in the game given the positions of all pieces
Some hints since I can't comment: I'd suggest trying to rotate the board by 45 degrees. Then your problem essentially reduces to your queen going right/upwards. The rest can then be solved with Segment Tree or Treap.