A program that will move the knight around a chessboard The

A program that will move the knight around a chessboard. The board is represented by an 8-by-8 double-subscripted array board. Each of the squares is ini- Chapter 4 Ids from an array that whether the pen is curfloor with its pen up. Chapter 4  Arrays 299 tialized to zero. We describe each of the eight possible moves in terms of both their horizontal and vertical components. For example, a move of type O, consists of moving two squares horizontally to the right and one square vertically upward. Move 2 consists of moving one square horizontally to the left and two squares vertically upward. Horizontal moves to the left and vertical moves upward are indicated with negative numbers. The eight moves may be described by two single-subscripted arrays, horizontal and vertical, as follows: horizotal [0] = 2, horizontal [1] = 1, horizontal [2] = -1, horizontal [3] = -2, horizontal [4] = -2, horizontal [5] = -1, horizontal [6] = 1, horizontal [7] = 2, vertical [0] = -1, vertical [1] = -2, vertical [2] = -2, vertical [3] = -1, vertical [4] = 1, vertical [5] = 2, vertical [6] = 2, vertical [7] = 1. Let the variables currentRow and currentCoIumn indicate the row and column of the knight\'s current position. To make a move of type moveNumber, where moveNumber is between O and 7, your program uses the statements, currentRow += vertical [ moveNumber ]; currentCoIumn horizontal [ moveNumber ]; Keep a counter that varies from 1 to 64. Record the latest count in each square the knight moves to. Remember to test each potential move to see if the knight has already visited that square, and, of course, test every potential move to make sure that the knight does not land off the chessboard. Write a program to move the knight around the chessboard. Please write in C++!! Any help would be greatly appreciated!! Thank you in advance!!

Solution

#include<iostream>

#define N 8

using namespace std;

// defines a structure for chess moves

typedef struct chess_moves {
  
// \'x\' and \'y\' coordinates on chess board
  
int x,y;

}chess_moves;

// displays the knight tour solution

void printTour(int tour[N][N]) {
  
int i,j;
  
for (i = 0; i < N; i++)
{
  
for (j = 0; j < N; j++)
{
  
cout<<tour[i][j]<<\"\\t\";

}
cout<<endl;
}
}

// check if the next move (as per knight\'s constraints) is possible

bool isMovePossible(chess_moves next_move, int tour[N][N]) {

int i = next_move.x;

int j = next_move.y;
  
if ((i >= 0 && i < N) && (j >= 0 && j < N) && (tour[i][j] == 0))

return true;

return false;

}

// recursive function to find a knight tour
bool findTour(int tour[N][N], chess_moves move_KT[],
  
chess_moves curr_move, int move_count)
{
int i;

chess_moves next_move;

if (move_count == N*N-1) {

// Knight tour is completed i.e all cells on the

// chess board has been visited by knight once

return true;
}

  
// try out the possible moves starting from the current coordinate

for (i = 0; i < N; i++)
{
// get the next move

next_move.x = curr_move.x + move_KT[i].x;

next_move.y = curr_move.y + move_KT[i].y;

  
if (isMovePossible(next_move, tour))
{

// if the move is possible

// increment the move count and store it in tour matrix
  
tour[next_move.x][next_move.y] = move_count+1;
  
if (findTour(tour, move_KT, next_move, move_count+1) == true) {

return true;
  
}
  
else {
// this move was invalid, try out other possiblities
  
tour[next_move.x][next_move.y] = 0;
  
}
  
}
  
}
  

return false;

}

// wrapper function
void knightTour()
{
int tour[N][N];
  
int i,j;

// initialize tour matrix
  
for (i = 0; i < N; i++)
{
  
for (j = 0; j < N; j++)
{
  
tour[i][j] = 0;
}

}

// all possible moves that knight can take

chess_moves move_KT[8] = { {2,1},{1,2},{-1,2},{-2,1},

{-2,-1},{-1,-2},{1,-2},{2,-1}
};

// knight tour starts from coordinate (0,0)

chess_moves curr_move = {0,0};

// find a possible knight tour using a recursive function
  
// starting from current move
  
if(findTour(tour, move_KT, curr_move, 0) == false)
{

cout<<\"\ Knight tour does not exist\";
  
}

else {

cout<<\"\ Tour exist ...\ \";
  

printTour(tour);
}
}

// main

int main() {
knightTour();
cout<<end;
  
return 0;

}