Masrur Sarar

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

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...