Queens That Can Attack the King

Queens That Can Attack the King

What is this problem about?

The Queens That Can Attack the King problem gives you positions of chess queens on an 8×8 board and the position of the king. Find all queens that can directly attack the king — meaning no other queen blocks the line of sight between them. This coding problem simulates directional ray casting from the king's position. The array, matrix, and simulation interview pattern is the core.

Why is this asked in interviews?

Media.net and Microsoft ask this to test systematic directional search — extending outward from a central point in all 8 directions and stopping at the first queen found (or board edge) in each direction.

Algorithmic pattern used

Ray casting from king in 8 directions. For each of the 8 directions (horizontal, vertical, diagonal): extend one step at a time from the king's position. If a queen is found, add it to results and stop searching that direction. If the board boundary is reached, stop. This runs in O(8 × 8) = O(1) effectively.

Example explanation

King at (4,4). Queens at [(0,1),(1,0),(3,3),(4,0),(1,4),(0,7),(1,6)].

• Direction (-1,-1) (up-left diagonal): (3,3) queen found. Add.
• Direction (0,-1) (left): (4,0) no queen at (4,3),(4,2),(4,1),(4,0)→queen at (4,0). Add.
• Direction (-1,0) (up): (1,4)→check (3,4),(2,4),(1,4) queen. Add. Continue all 8 directions. Return attacking queens.

Common mistakes candidates make

• Not stopping after finding the first queen in each direction.
• Missing diagonal directions (should be all 8, not just 4).
• Checking all queens instead of ray-casting from king (O(n²) vs O(64)).
• Off-by-one in boundary checking.

Interview preparation tip

Ray casting in 8 directions from a center point is a fundamental simulation technique. Define direction vectors as all combinations of (-1,0,1) × (-1,0,1) excluding (0,0). Extend outward, stopping on first hit or boundary. This pattern appears in: "visible cells in a grid," "lighthouses," "blocked line of sight." Practice implementing clean directional loops with early termination.