Answer to Question #221490 in C++ for Sunny

Question

 Chess Game Knight’s travails. You are required to do the following: 1. Explain how you can ensure that any move do not go off the board. 2. Choosing a search algorithm for finding the shortest path for the knight’s travails. 3. Defend your choice of an appropriate search algorithm to find the best possible move from the starting square to the ending square. 4. Creating a script for a board game and a knight. 5. Create a diagrammatical tree structure, to illustrate all possible moves of the knight as children in the tree structure. In this task, you need to understand two algorithms which can be helpful, the BreadthFirst Search which utilizes the Queue data structure to find the shortest path and the Depth-First Search which can traverse a Stack data structures. Hint: Develop a data structure similar to binary trees. Using a standard 8 X 8 chessboard, show the knight’s movements in a game.

Answer 1

#include <iostream>
using namespace std;
struct cell {
    int x, y;
    int dis;
    cell() {}
    cell(int x, int y, int dis)
        : x(x), y(y), dis(dis)
    {
    }
};
 
bool isInside(int x, int y, int N)
{
    if (x >= 1 && x <= N && y >= 1 && y <= N)
        return true;
    return false;
}
 
int minStepToReachTarget(
    int knightPos[], int targetPos[],
    int N)
{
    int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };
    int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
 
    queue<cell> q;
 
    q.push(cell(knightPos[0], knightPos[1], 0));
 
    cell t;
    int x, y;
    bool visit[N + 1][N + 1];
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            visit[i][j] = false;
    visit[knightPos[0]][knightPos[1]] = true;
    while (!q.empty()) {
        t = q.front();
        q.pop();
        if (t.x == targetPos[0] && t.y == targetPos[1])
            return t.dis;
        for (int i = 0; i < 8; i++) {
            x = t.x + dx[i];
            y = t.y + dy[i];
 
           
            if (isInside(x, y, N) && !visit[x][y]) {
                visit[x][y] = true;
                q.push(cell(x, y, t.dis + 1));
            }
        }
    }
}
 
int main()
{
    int N = 30;
    int knightPos[] = { 1, 1 };
    int targetPos[] = { 30, 30 };
    cout << minStepToReachTarget(knightPos, targetPos, N);
    return 0;
}