patternMinor
Knight on a chessboard
Viewed 0 times
chessboardknightstackoverflow
Problem
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$
Constraints
$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.
$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$
Constraints
$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.
Solution
You could use the breadth first search (BFS) algorithm. The knight may move at most to eight cell (from a single position) which means that if each cell is treated as a single node then degree of each node is at most eight and so the number of edges is at most $\frac{8N}{2} = 4N$, where $N = n^2$ is the total number of nodes/cells and $n\times n$ is the size of the chessboard. Since BFS' complexity is $O(V + E)$ your algorithm will run in $O(N+ 4N) = O(N)$.
Warning: do not try to create a graph from the chessboard. It is overkill. You just need to maintain queue and mark all visited cells as you iterate. While the knight is at the position $(i,j)$ just compute all possible moves from this position and push them into the queue if they are not already visited and you haven't yet reached $(n-1, n-1)$.
Warning: do not try to create a graph from the chessboard. It is overkill. You just need to maintain queue and mark all visited cells as you iterate. While the knight is at the position $(i,j)$ just compute all possible moves from this position and push them into the queue if they are not already visited and you haven't yet reached $(n-1, n-1)$.
Context
StackExchange Computer Science Q#80297, answer score: 6
Revisions (0)
No revisions yet.