Shortest Path on Chess Board (BFS)

Question

Given a fixed-size chess board, find the shortest path between two positions (e.g., for a knight or similar chess piece). You must implement the solution from scratch including main(), custom function signatures with input/output, and your own test cases. The base problem uses a fixed board size. Candidate must discuss tradeoffs between BFS and DFS before choosing an approach.

AceOffer · Accepted Answer

Given a fixed-size chess board, find the shortest path between two positions (e.g., for a knight or similar chess piece). You must implement the solution from scratch including main(), custom function signatures with input/output, and your own test cases. The base problem uses a fixed board size. Candidate must discuss tradeoffs between BFS and DFS before choosing an approach.

Reported follow-ups:
1. What if some cells on the board are blocked/impassable? How would you modify your solution? (when: After base solution is working correctly)
2. What if the chess board is infinitely large? How would you handle that? (when: After blockage follow-up)

**Alternative approaches:** DFS (Does not guarantee shortest path; may explore deep paths unnecessarily. Simpler to implement recursively but wrong for shortest-path problems.); BFS with symmetry optimization (Convert (x, y) to first quadrant using symmetry to reduce state space; also allow slightly negative coordinates (e.g., -2) to handle edge cases near the origin. Harder to think of under interview pressure.)

Shortest Path on Chess Board (BFS)

Problem Overview

Follow-up Arc

Approach Trade-offs

Practice

Approach	Notes
DFS	Does not guarantee shortest path; may explore deep paths unnecessarily. Simpler to implement recursively but wrong for shortest-path problems.
BFS with symmetry optimization	Convert (x, y) to first quadrant using symmetry to reduce state space; also allow slightly negative coordinates (e.g., -2) to handle edge cases near the origin. Harder to think of under interview pressure.