Board Moves: Find All Valid Moves for a Piece on a Game Board
Question Details
Round 1 Coding
Problem
Given an N x N board and a piece at position (r, c),
return all valid positions the piece can move to in one step. The piece moves like a chess knight (L-shape). Positions that fall off the board are invalid.
python
def valid_moves(board_size: int, row: int, col: int) -> list[tuple[int, int]]:
...
Example
valid_moves(8, 4, 4)
-> [(2,3),(2,5),(3,2),(3,6),(5,2),(5,6),(6,3),(6,5)]
valid_moves(8, 0, 0)
-> [(1,2),(2,1)]
valid_moves(3, 1, 1)
-> [(0,3-invalid),(2,3-invalid)...] -> []
# A knight at center of a 3x3 board has no valid moves.
Follow-ups
1. Extend this: given a starting position and k moves,
return all positions reachable in exactly k knight moves. What is the time complexity?
2. How would you modify your solution for a different piece — e.g., a bishop or queen?
3. If the board has blocked cells, how do you incorporate that constraint?
4. Find the minimum number of moves for a knight to travel from (r1,c1) to (r2,c2). What algorithm applies?
Full Details
Round 1 Coding
Problem
Given an N x N board and a piece at position (r, c),
return all valid positions the piece can move to in one step. The piece moves like a chess knight (L-shape). Positions that fall off the board are invalid.
python
def valid_moves(board_size: int, row: int, col: int) -> list[tuple[int, int]]:
...
Example
valid_moves(8, 4, 4)
-> [(2,3),(2,5),(3,2),(3,6),(5,2),(5,6),(6,3),(6,5)]
valid_moves(8, 0, 0)
-> [(1,2),(2,1)]
valid_moves(3, 1, 1)
-> [(0,3-invalid),(2,3-invalid)...] -> []
# A knight at center of a 3x3 board has no valid moves.
Follow-ups
1. Extend this: given a starting position and k moves,
return all positions reachable in exactly k knight moves. What is the time complexity?
2. How would you modify your solution for a different piece — e.g., a bishop or queen?
3. If the board has blocked cells, how do you incorporate that constraint?
4. Find the minimum number of moves for a knight to travel from (r1,c1) to (r2,c2). What algorithm applies?
About This Question
This is a reported interview question from a glean interview during the phone round.