AlgoVisual - Interactive Algorithm Visualization

This problem asks us to simulate the movement of three chess pieces: King, Knight, and Queen.

Given an n x n binary grid board (0 = empty, 1 = occupied), a piece type, and a starting position [r, c], return all unoccupied cells reachable in one move.

Examples for Chess Moves (the white cells are 0's, numbers are 1's).

Movement Rules:

King: Moves 1 step in any of the 8 directions (horizontal, vertical, diagonal).
Knight: Moves in an 'L' shape (2 steps one way, 1 step perpendicular). It can jump over obstacles.
Queen: Moves any number of steps in any of the 8 directions until blocked by an obstacle or the board edge.

Examples:

King: r = 3, c = 5. Output: [[2, 5], [3, 4], [4, 4], [4, 5]].
Knight: r = 4, c = 3. Output: [[2, 2], [3, 5], [5, 5]].
Queen: r = 4, c = 4. Output: [[3, 4], [3, 5], [4, 0], [4, 1], [4, 2], [4, 3], [4, 5], [5, 3], [5, 4], [5, 5]].

1def getValidMoves(board: List[List[int]], piece: str, r: int, c: int) -> List[List[int]]:

2 n = len(board)

3 moves = []

5 # 8 directions for King and Queen

6 dirs_8 = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]

8 if piece == "king":

9 for dr, dc in dirs_8:

10 nr, nc = r + dr, c + dc

11 if 0 <= nr < n and 0 <= nc < n and board[nr][nc] == 0:

12 moves.append([nr, nc])

14 elif piece == "knight":

15 # 8 L-jumps

16 jumps = [(-2,-1), (-2,1), (-1,-2), (-1,2), (1,-2), (1,2), (2,-1), (2,1)]

17 for dr, dc in jumps:

18 nr, nc = r + dr, c + dc

19 if 0 <= nr < n and 0 <= nc < n and board[nr][nc] == 0:

20 moves.append([nr, nc])

22 elif piece == "queen":

23 # Slide until blocked

24 for dr, dc in dirs_8:

25 nr, nc = r + dr, c + dc

26 while 0 <= nr < n and 0 <= nc < n:

27 if board[nr][nc] == 1:

28 break # Blocked

29 moves.append([nr, nc])

30 nr += dr

31 nc += dc

33 return moves