Knight on a chessboard

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.

• What algorithm do you mean by the brute-force? Why not try BFS? Commented Aug 21, 2017 at 17:49
• Brute force would be iterate though all possible moves. I don't know what BFS/DFS is be I will try and find it. Commented Aug 21, 2017 at 17:51
• Breadth first search (BFS) is a graph traversal algorithm which may be used to find the shortest path between two nodes in an unweighted graph. Commented Aug 21, 2017 at 17:53
• @fade2black That is what I was thinking about but I did not have the queue part. I will give it a try. Commented Aug 21, 2017 at 18:02
• This made hot network question Commented Aug 21, 2017 at 21:51

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

• OK I think I know how use that to traverse all the move. When I hit $(n-1, n-1)$ how do I know how many moves? Will it be the queue size. How do I know that is the minimum? Commented Aug 21, 2017 at 18:12
• @Paparazzi, Q2: you have at most $25\times 25$ chessboard, so the maximum number of nodes is $625$. Is it too big to store in a queue? Commented Aug 21, 2017 at 18:23
• @Paparazi Q1: Your question is implementation specific. For example, when you store the node/cell in the queue you could store the distance from the (0,0) together with the nodes themselves (as a single structure {node, dist}). So every time you expand a node just set the children's distance plus parent's distance plus one . Commented Aug 21, 2017 at 18:26
• @Paparazzi Q3: BFS always computes the shortest path in an unweighted graph. So, when you reach \$ (n-1,n-1)4 it will be the shortest path. Commented Aug 21, 2017 at 18:27
• Note that being O(n) in the number of cells is O(n^2) for the 'n' in the problem, because a chessboard which is n x n has n^2 cells. Commented Aug 21, 2017 at 22:21

I am going to delete this

Just showing the accepted answer how I got the step count

public static void Visit(int row, int col, int n, Queue<int> queue, bool[] visited)
{
if (row < 0 || col < 0 || row >= n || col >= n)
return;
int position = row * n + col;
if (visited[position])
return;
visited[position] = true;
queue.Enqueue(position);
}
public static int KnightHelper(int n, int i, int j)
{
if (i == j)
{
return ((n - 1) % i == 0) ? (n - 1) / i : -1;
}

//try bfs
bool[] visited = new bool[n * n];
Queue<int> queue = new Queue<int>();
int steps = 0;
queue.Enqueue(0);
while (queue.Count > 0)
{
int count = queue.Count();
for (int m = 0; m < count; m++)
{
int position = queue.Dequeue();
int row = (position / n);
int col = (position % n);

if (row == n - 1 && col == n - 1)
{
// Found solution.
return steps;
}

Visit(row + i, col + j, n, queue, visited);
Visit(row + i, col - j, n, queue, visited);
Visit(row + j, col + i, n, queue, visited);
Visit(row + j, col - i, n, queue, visited);
Visit(row - i, col + j, n, queue, visited);
Visit(row - i, col - j, n, queue, visited);
Visit(row - j, col + i, n, queue, visited);
Visit(row - j, col - i, n, queue, visited);
}
steps++;
}
return -1;
}