Queens That Can Attack the King: Direction Scanning

On an 8x8 chessboard, you are given the positions of black queens and one white king. Return the coordinates of all queens that can directly attack the king. A queen can attack along its row, column, or any diagonal, but only if no other queen is blocking the path between them.

This is LeetCode 1222: Queens That Can Attack the King.

Why this problem matters

The 8-direction scanning pattern shows up in many grid problems. Any time you need to look outward from a point along rows, columns, and diagonals, you are using the same idea. Chess problems, word search, and "nearest obstacle" problems all rely on it. Once the pattern is automatic, you can apply it to any grid problem that involves line-of-sight or directional traversal.

The key insight

Your first instinct might be to check each queen and see if it can reach the king. That works, but you have to trace the path from each queen back to the king to check for blockers. There is a simpler approach: scan outward from the king in all 8 directions. The first queen you encounter in each direction is one that can attack. Any queen behind it is blocked.

This flips the problem from "which queens reach the king" to "what does the king see in each direction." Since the board is fixed at 8x8, each direction scan visits at most 7 cells. Eight directions times seven cells gives a constant amount of work.

The solution

def queens_attack_the_king(queens, king):
    queen_set = set(map(tuple, queens))
    result = []
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1),
                  (-1, -1), (-1, 1), (1, -1), (1, 1)]

    for dr, dc in directions:
        r, c = king
        while True:
            r += dr
            c += dc
            if r < 0 or r > 7 or c < 0 or c > 7:
                break
            if (r, c) in queen_set:
                result.append([r, c])
                break

    return result

The algorithm starts from the king and walks outward in each of the 8 directions. For each direction, it steps one cell at a time. If it finds a queen, it adds that queen to the result and stops scanning that direction. If it walks off the board, it moves on to the next direction.

The queen_set is a hash set that gives O(1) lookups. Without it, you would need to scan the queen list for every cell you visit, which adds unnecessary overhead.

The break after finding a queen is what handles the "blocking" logic. You only care about the first queen in each direction. Any queens further along that line are irrelevant because the first queen blocks the path.

Visual walkthrough

Let's trace through the algorithm step by step. The king is at (3,4) and seven queens are scattered across the board. Watch how scanning from the king finds the first queen in each direction.

Six of the seven queens can attack the king. The queen at (7,3) cannot because it is not aligned with the king along any row, column, or diagonal. The scanning approach finds all six attackers without ever needing to check the blocked queen.

Complexity analysis

Time is O(1) because the board is always 8x8. We scan 8 directions, and each direction visits at most 7 cells. That is 8 * 7 = 56 cell checks at most, which is a constant. The initial set construction is O(Q) where Q is the number of queens, but Q is at most 63, so that is also effectively constant.

Space is O(Q) for the hash set of queen positions. On an 8x8 board, Q is at most 63, so this is bounded by a constant. The result list holds at most 8 queens (one per direction).

The building blocks

1. Eight-direction traversal

directions = [(-1, 0), (1, 0), (0, -1), (0, 1),
              (-1, -1), (-1, 1), (1, -1), (1, 1)]

for dr, dc in directions:
    r, c = start_r, start_c
    while 0 <= r + dr <= 7 and 0 <= c + dc <= 7:
        r += dr
        c += dc

This is the standard pattern for scanning all 8 directions from a point on a grid. The direction vectors cover north, south, west, east, and the four diagonals. You will reuse this exact pattern in problems like N-Queens constraint checking, bishop attack detection, and word search in all directions.

2. Set-based lookup for positions

queen_set = set(map(tuple, queens))

if (r, c) in queen_set:
    result.append([r, c])
    break

Converting a list of positions to a set lets you check "is there a piece at this cell?" in O(1) time. The alternative, scanning the list each time, would be O(Q) per check. This pattern appears any time you need fast membership tests on grid coordinates, for example checking obstacles, walls, or visited cells.

Edge cases

• No queens on the board: the result is an empty list. Every direction scan walks to the edge without finding anything.
• Queens in all 8 directions: the result contains 8 queens, one per direction. This is the maximum possible.
• Multiple queens along the same line: only the closest one to the king is returned. The first break ensures queens behind it are ignored.
• King in a corner: only 3 directions stay on the board (2 cardinal, 1 diagonal). The other 5 directions immediately go out of bounds.
• King on an edge but not a corner: 5 directions stay on the board. The remaining 3 go out of bounds after the first step.
• All queens are on the same row or column: at most 2 can attack (one from each side of the king along that line).

From understanding to recall

The direction scanning pattern is easy to understand but surprisingly easy to get wrong under pressure. Do you remember all 8 direction vectors? Do you handle the board boundary check before or after stepping? Do you break after finding the first queen or after adding it? These details matter, and they are exactly the kind of thing you forget when you are nervous.

Spaced repetition turns understanding into reflex. You write the 8-direction loop from memory, get the boundary check right, and handle the early termination correctly. After a few sessions, scanning from a target outward becomes something you do without thinking. The next time a grid problem asks "what can this cell see," the code writes itself.

Related posts

• N-Queens - Classic chess problem using row/column/diagonal constraint checking
• Number of Islands - Grid traversal in multiple directions
• Rotting Oranges - Multi-directional spreading on a grid

CodeBricks breaks Queens That Can Attack the King into its direction scanning and set lookup building blocks, then drills them with spaced repetition until the pattern is automatic. You type the 8-direction loop and the scan-until-found logic from memory until there is no hesitation. When a matrix problem appears in your interview, you do not pause to think about direction vectors. You just write them.