Search code examples
c++chess

The minimum number of steps for a chess knight to reach a certain position on a chessboard

There is an unlimited chessboard,
from the console we enter how many examples there will be and how many chess knights are on the board, and their starting positions (that is, where they are), and the points to which the knights must go in the least number of steps.

Here's what it should look like:

  • 2 - number of examples
  • 1 - the number of chess knights
  • 5 5 - the starting point
  • 5 6 - the final point
  • 2 - the number of chess knights
  • 0 0 - the starting point of the first knight
  • 1 0 - the starting point of the second knight
  • 0 1 - the final point of the first knight
  • 1 1 - the final point of the second knight

Answer:

  • 3 - the answer for the first example
  • 4 - the answer for the second example

The problem is that it doesn't work out that way, because with the first data set everything is fine, but with the second it does not work out the correct answer.
If we take the points separately, then the answer in the second data set is 6 (3 for the first knight and 3 for the second knight).
I have guesses how to solve it, but it does not work.

The conjecture is that when the second knight begins to move, it passes the same points that the first knight passed (the second example) and you probably need to write down the conditions if the first knight was already at these positions, then the second cannot pass them again.

The second conjecture is that you need to write down the conditions for the board and make it unlimited, and make the knight walk the negative values of the chessboard.

Here is a sample photo (below):

Please help, I will be very grateful !!!

#include <iostream>
#include <set>
#include <queue>
#include <climits>
using namespace std;

#define N 8

// Below arrays details all 8 possible movements 
// for a knight
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };

// Check if (x, y) is valid chess board coordinates
// Note that a knight cannot go out of the chessboard
bool valid(int x, int y)
{
    if (x < 0 || y < 0 || x >= N || y >= N)
        return false;

    return true;
}

// queue node used in BFS
struct Node
{
    // (x, y) represents chess board coordinates
    // dist represent its minimum distance from the source
    int x, y, dist;

    // Node constructor
    Node(int x, int y, int dist = 0): x(x), y(y), dist(dist) {}

    // As we are using struct as a key in a std::set, 
    // we need to overload < operator
    // Alternatively we can use std::pair<int, int> as a key
    // to store coordinates of the matrix in the set

    bool operator<(const Node& o) const
    {
        return x < o.x || (x == o.x && y < o.y);
    }
};

// Find minimum number of steps taken by the knight 
// from source to reach destination using BFS
int BFS(Node src, Node dest)
{
    // set to check if matrix cell is visited before or not
    set<Node> visited;

    // create a queue and enqueue first node
    queue<Node> q;
    q.push(src);

    // run till queue is not empty
    while (!q.empty())
    {
        // pop front node from queue and process it
        Node node = q.front();
        q.pop();

        int x = node.x;
        int y = node.y;
        int dist = node.dist;

        // if destination is reached, return distance
        if (x == dest.x && y == dest.y)
            return dist;

        // Skip if location is visited before
        if (!visited.count(node))
        {
            // mark current node as visited
            visited.insert(node);

            // check for all 8 possible movements for a knight
            // and enqueue each valid movement into the queue
            for (int i = 0; i < 8; ++i) 
            {
                // Get the new valid position of Knight from current
                // position on chessboard and enqueue it in the 
                // queue with +1 distance
                int x1 = x + row[i];
                int y1 = y + col[i];

                if (valid(x1, y1))
                    q.push({x1, y1, dist + 1});
            }
        }
    }

    // return INFINITY if path is not possible
    return INT_MAX;
}

// main function
int main()
{
    // source coordinates
    Node src = {0, 7};

    // destination coordinates
    Node dest = {7, 0};

    cout << "Minimum number of steps required is " << BFS(src, dest);

    return 0;
}

sample photo

Solution

  • This is an answer assuming the ending positions are not linked to the knights (any knight can end up in any ending position). This is an algorithmic question independent of programming languages, so I won't show any code.

    The simplest, but least efficient way would be to assume each knight has a single required final position. You assign all permutations of the final positions to the knights by index and for each permutation, calculate the result. Finally, you return the minimal result. In your example, one result would be 6 (original mapping), the other one would be 4 (swapped final positions, the only other permutation), so you'd get 4. The problem with this approach is that for n knights, you'll have n! permutations to consider.

    The greedy approach would be for each knight to move until it hits one of the final spots, then for the other to hop to the other. This would work for your example but goes wrong for this one:

    • Knights: (5,4), (2,1); Final positions: (3,3), (9,6)

    First knight would move

    • (5,4) -> (3,3)

    and is done (1 step), second knight will then have to move

    • (2,1) -> (4,2) -> (5,4) -> (7,5) -> (9,6)

    This needs 4 steps, making a total of 5. However, the optimal solution is:

    • (5,4) -> (7,5) -> (9,6)
    • (2,1) -> (3,3)

    Which are 3 steps. So we see, a naive greedy algorithm does not necessarily yield a correct result.

    However, we can do better with a greedy approach: First, calculate the distances between each knight/final position pair, and store them (using your original algorithm).

    Our previous example would look like this:

    (5,4)        <- first knight
  (3,3) = 1  <- distance to first final position
  (9,6) = 2  <- distance to second final position
(2,1)        <- second knight
  (3,3) = 1
  (9,6) = 4

    Once you have calculated those, the algorithm will subsequently assign an ending position to the knights. It will work like this:

    Loop over all knights that do not yet have an ending position. For each knight, mark the nearest final position and calculate the penalty on the other knights. The penalty is the maximum of additional moves for all other knights that have not yet been assigned. For example, selecting (3,3) for the knight at (5,4) would have a penalty of 3, since the other knight will now need to move 3 additional steps (as we marked its nearest final position). However, selecting (3,3) for the knight at (2,1) has a penalty of 1 because the other knight only needs to move one additional step.

    After you calculated all penalties, assign the knight with the smallest penalty its nearest final position. Loop until all knights have been assigned a final position.

    This algorithm is correct for both your original example and my example, however I don't know whether it's always correct. You'd need to prove that.