Problem #3. (Programming) Knight (20 pts) Given a squared chess board, find the
ID: 3589133 • Letter: P
Question
Problem #3. (Programming) Knight (20 pts) Given a squared chess board, find the minimum number of steps taken by a Knight to reach desired destination from its given source position. As illustrated in the right figure, Knight can move to 8 different locations by a single step. For instance, we need at least 3 steps to move the Knight at (2,4) to the goal position (6,1). Specifically, the Knight can move the following path: (2,4) (3,2) (4,0) (6,1). Note that, locations are represented by (vertical, horizontal) coordinates and left-upper corner is (0.0) similar to the array in C/C+. Your program is required to get an input from "input _knights.txt" and write the result to a file "output knight.txt" as the following example: output knight.txt input knight.txt 24 6 1 The first value in the input file indicates the chess board size N 5 s N s 15). The second and third lines are the number of steps from the unreachable. Your program has to produce an answer within 5 seconds source and destination locations, repsectively. The output file only contains the minimum source to the destination. You can output-1", if the destination is You are asked to briefly describe your algorithm in the report and name your source code file "ID_Al_Knight.cppExplanation / Answer
#include<iostream>
#include<fstream.h>
#define M 8
using namespace std;
// chess moves structure
typedef struct chess_moves {
// x and y are coordinates of chess board
int x,y;
}chess_moves;
// find if the next move is possible
bool isMovePossible(chess_moves next_move, int tour[M][M]) {
int i = next_move.x;
int j = next_move.y;
if ((i >= 0 && i < M) && (j >= 0 && j < M) && (tour[i][j] == 0))
return true;
return false;
}
// recursive function for a knight tour
bool findTour(int tour[M][M], chess_moves move_KT[],
chess_moves curr_move, int move_count) {
int i;
chess_moves next_move;
if (move_count == M*M-1) {
// Knight tour is completed i.e all cells on the
return true;
}
// displays the knight tour
void printTour(int tour[M][M]) {
ofstream outf(“out_knight.txt”);
int i,j;
for (i = 0; i < M; i++) {
for (j = 0; j < M; j++) {
outf<<tour[i][j]<<" ";
}
cout<<endl;
}
outf.close();
}
// try out the possible moves starting from the current coordinate
for (i = 0; i < M; 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[M][M];
int i,j;
// initialize tour matrix
for (i = 0; i < M; i++) {
for (j = 0; j < M; 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} };
ifstream inf(“input-knight.txt”);
int a,b;
inf>>a;
inf>>b
chess_moves curr_move = {a,b};
inf.close();
// 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 function
int main()
{
knightTour();
cout<<endl;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.