Python 3.6 Please provide a screenshot of code and output The Knight\'s Tour is

Question

Python 3.6

Please provide a screenshot of code and output

The Knight's Tour is an ancient puzzle. The objective is to move a knight, starting from any square on a chessboard, to every other square once as shown below. Note that the knight makes only L-shaped moves (two spaces in one direction and one space in a perpendicular direction). As shown in Figure below, the knight can move to eight squares. Write a program that displays the moves for the knight, as shown in below. When you click a cell, the knight is placed at the cell. This cell will be starting point for the knight. Clicking the Solve button to display the path for a solution.

Explanation / Answer

#include<stdio.h>
#define n 8

/*to check valid index of checkboard */
bool isprotected(int a, int b, int solution[n][n])
{
    return ( a >= 0 && a < n && b >= 0 &&
             b < n && solution[a][b] == -1);
}

/*print solution matrix*/
void print(int solution[n][n])
{
    for (int x = 0; x < n; x++)
    {
        for (int y = 0; y < n; y++)
            printf(" %2d ", sol[x][y]);
        printf(" ");
    }
}
/* if no tour is found,it returns false else true . backtracking approach is used. */
bool knighttour()
{
    int solution[n][n];

    /* matrix that show result is initialized*/
    for (int a = 0; a < n; a++)
        for (int b = 0; b < n; b++)
            solution[a][b] = -1;

    /* Next move of knight is defined */
    int x[8] = { 1, 2, -1, -1, -1, -2, -2, 2 };
    int y[8] = { 2, -2, 1, 1, -1, -2, -2, -1 };

    // knight initial position
    solution[0][0] = 0;

    // explore all path using backtracking
    if (solveknighttour(0, 0, 1, sol, x, y) == false)
    {
        printf("oops!no solution");
        return false;
    }
    else
        print(solution);

    return true;
}

//recursive function that implement backtracking
int solveknighttour(int a, int b, int moving, int solution[n][n],
                int x[n], int y[n])
{
   int k, next_x_m, next_y_m;
   if (moving == n*n)
       return true;

   for (k = 0; k < 8; k++)
   {
       next_x_m = a + x[k];
       next_y_m = b + y[k];
       if (isprotected(next_x_m, next_y_m, solution))
       {
         sol[next_x_m][next_y_m] = moving;
         if (solveknighttour(next_x_m, next_y_m, moving+1, solution,
                         x, y) == true)
             return true;
         else
             solution[next_x_m][next_y_m] = -1;
       }
   }

   return false;
}

int main()
{
    knighttour();
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.