Accelerated Knight: An O(1) Algorithm for Computing Minimum Knight Moves on an n × n Chessboard

Abstract

We present an O(1) time and O(1) space algorithm for computing the minimum number of knight moves between two squares on a finite n × n chessboard. Classical approaches use breadth-first search (BFS) and require O(n^2) time. Our algorithm exploits symmetry, a lowerbound threshold principle, and a parity adjustment to derive a closed-form solution. The only exceptions are a finite set of boundary cases near the corners and on boards of size at most 4×4, which are handled by a small lookup table. We prove correctness via a symmetry reduction, a lower-bound lemma, a complete infinite-board induction, and a finite-board boundary lemma. We validate the algorithm against BFS for all pairs on boards up to 50 × 50 and for random pairs on boards up to 1000 × 1000.