This is a Hackerrank challenge
$Knight$ is a chess piece that moves in an L shape. We define the possible moves of $Knight(a,b)$ as any movement from some position $(x_1, y_1)$ to $(x_2, y_2)$ satisfying either of the following:
$x_2 = x_1 \pm a$ and $y_2 = y_1 \pm b$, or
$x_2 = x_1 \pm b$ and $y_2 = y_1 \pm a$
Given the value of $n$ for a square chessboard, answer the following question for each $(a, b)$ pair where :
$1 \leq a \leq b \lt n$
$1 5 \leq n \leq 25$
What is the minimum number of moves it takes for $Knight$ to get from position $(0, 0)$ to position $(n-1, n-1)$? If it's not possible for the Knight to reach that destination, the answer is -1 instead.
If $a = b$ then it is simply $(n-1) / 2a$ if it is evenly divisible
What I cannot figure out is when some of the steps need to be backwards $x_2 \lt x_1$.
Can this be solved with an algorithm other than brute force?
If so what is the algorithm?
Brute force to me is iterate over all possible moves.
If brute force is it safe to assume $a$ and $b$ would never both be negative on a move? Answer is no. If brute force could it be limited to one diagonal or the other? Answer is no.