4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What algorithm do you mean by the brute-force? Why not try BFS? $\endgroup$ – fade2black Aug 21 '17 at 17:49
  • $\begingroup$ Brute force would be iterate though all possible moves. I don't know what BFS/DFS is be I will try and find it. $\endgroup$ – paparazzo Aug 21 '17 at 17:51
  • 2
    $\begingroup$ 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. $\endgroup$ – fade2black Aug 21 '17 at 17:53
  • $\begingroup$ @fade2black That is what I was thinking about but I did not have the queue part. I will give it a try. $\endgroup$ – paparazzo Aug 21 '17 at 18:02
  • 1
    $\begingroup$ This made hot network question $\endgroup$ – paparazzo Aug 21 '17 at 21:51
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – paparazzo Aug 21 '17 at 18:12
  • $\begingroup$ @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? $\endgroup$ – fade2black Aug 21 '17 at 18:23
  • $\begingroup$ @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 . $\endgroup$ – fade2black Aug 21 '17 at 18:26
  • $\begingroup$ @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. $\endgroup$ – fade2black Aug 21 '17 at 18:27
  • 1
    $\begingroup$ 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. $\endgroup$ – DanTilkin Aug 21 '17 at 22:21
1
$\begingroup$

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;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.