//Please show the answer in a whole code and capture the outputs that match the below output answers.

/* * Instructions: * * 1. Only complete the functions specified below. Do not create any additional function. * 2. Use Visual Studio 2019 to build, test and run your code. * 3. Do not include any additional header or library. * */

#include #include #include #include

#define N 5 // chessboard size is NxN #define INIT_X 0 // initial x position of the knight #define INIT_Y 0 // initial y position of the knight

using namespace std;

/* * A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. * * A knight can move in these 8 directions. The relative coordinates of the next move * of a knight are defined in xMove[] and yMove[] based on the 8 positions marked below. * * xMove[] is for the next value of x coordinate. * yMove[] is for the next value of y coordinate. * . . . . . . . . . M . M . . . M . . . M . . . . K . . . where K is at (0,0) . M . . . M . <--- M at (2,1) . . M . M . . <--- M at (1,2) . . . . . . . * */ const int xMove[8] = {2, 1, -1, -2, -2, -1, 1, 2}; const int yMove[8] = {1, 2, 2, 1, -1, -2, -2, -1};

void printSolution(int sol[N][N]);

//-------------------------- functions to be implemented by you

/* * * This recursive function finds knight tours using backtracking. It * prints out all possible tours found. * * - The argument (x,y) indicates the current position of knight. * - The argument 'step' indicates the n-th move of the tour. * - The argument chessboard[][] is the chessboard. * - The argument 'count' is the number of solutions found. * */ void solve(int x, int y, int step, int chessboard[N][N], int& count) {

}

//-------------------------- functions prepared for you

/* * A utility function to print solution matrix sol[N][N] */ void printSolution(int sol[N][N]) { for (int x = 0; x < N; x++) { for (int y = 0; y < N; y++) cout << setw(3) << sol[x][y]; cout << endl; } }

/* * Driver program to test above functions. * * The program should output 304 complete knight tours. * Please refer to the expected program output shown below. */ int main(int argc, char** argv) {

// number of solutions (complete tour) found int count = 0; // initialize chessboard int chessboard[N][N]; for (int x = 0; x < N; x++) for (int y = 0; y < N; y++) chessboard[x][y] = -1;

// set the knight to its initial position chessboard[INIT_X][INIT_Y] = 0; // tour starts from (0,0) solve(INIT_X, INIT_Y, 1, chessboard, count);

return 0; }

/***************************************************************************** Expected Program Output Note that the output order of these 304 tours can be different. *****************************************************************************

Solution 1: 0 5 14 9 20 13 8 19 4 15 18 1 6 21 10 7 12 23 16 3 24 17 2 11 22

Solution 2: 0 5 10 17 20 11 16 19 4 9 6 1 14 21 18 15 12 23 8 3 24 7 2 13 22

Solution 3: 0 5 10 15 20 11 14 19 4 9 6 1 12 21 16 13 18 23 8 3 24 7 2 17 22

Solution 4: 0 5 16 11 20 15 10 19 4 17 6 1 8 21 12 9 14 23 18 3 24 7 2 13 22

Solution 5: 0 11 16 5 20 17 4 19 10 15 12 1 8 21 6 3 18 23 14 9 24 13 2 7 22

Solution 6: 0 15 10 5 20 9 4 19 14 11 16 1 12 21 6 3 8 23 18 13 24 17 2 7 22

Solution 7: 0 17 10 5 20 9 4 19 16 11 18 1 14 21 6 3 8 23 12 15 24 13 2 7 22

Solution 8: 0 9 14 5 20 15 4 19 8 13 10 1 6 21 18 3 16 23 12 7 24 11 2 17 22

Solution 9: 0 15 4 9 20 5 10 19 14 3 18 1 16 21 8 11 6 23 2 13 24 17 12 7 22

Solution 10: 0 11 4 17 20 5 16 19 12 3 10 1 8 21 18 15 6 23 2 13 24 9 14 7 22

//Solution ......