//ONLY C++ DESCRIPTION Write a program that finds the shortest sequence of Knigh
ID: 3540021 • Letter: #
Question
//ONLY C++
DESCRIPTION
Write a program that finds the shortest sequence of Knight moves from a starting square to a target square in a mini chess board.
The mini chess board consists of 4 by 4 squares. Each square is labeled by a number from 0 to 15 as shown below.
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
The user provides the starting square number (say 0) and the ending square number (say 10). The program will display the shortest sequence of knight moves from starting square to the ending square (say 0, 9, 2, 4, 10).
#include< iostream>
using namespace std;
struct ItemType
{
int path [10];//An array containing a list of vertices along the path
//from the start vertex to this vertex.
int pathlen; //The length of the occupied part of the above array i.e.
//the length of the path stored in the above array.
};
struct Node
{
int path [10];//An array containing a list of vertices along the path
//from the start vertex to this vertex.
int pathlen; //The length of the occupied part of the above array i.e.
//the length of the path stored in the above array.
ItemType * link; //Link to the next item node.
};
//write these classes
class IntQue
{
private:
Node * head;
public:
bool isEmpty();
void enque (int n);
void deque(int& n);
};
class ItemQue
{
private:
Node * head;
public:
bool isEmpty();
void enque (ItemType item);
void deque(ItemType & item);
};
bool IntQue::isEmpty()
{
return false;
}
void IntQue::enque (int n)
{
}
void IntQue::deque(int& n)
{
}
bool ItemQue::isEmpty()
{
return false;
}
void ItemQue::enque (ItemType item)
{
}
void ItemQue::deque(ItemType & item)
{
}
void getNextSquares (int square, IntQue & q)
{
int nextSquare;
int row = square / 4;
int col = square % 4;
//upward moves
if (row - 2 >= 0 && col + 1 <= 3)
{
nextSquare = square - 7;
q.enque (nextSquare);
}
if (row - 2 >= 0 && col - 1 >= 0)
{
nextSquare = square - 9;
q.enque (nextSquare);
}
if (row - 1 >= 0 && col + 2 <= 3)
{
nextSquare = square - 2;
q.enque (nextSquare);
}
if (row - 1 >= 0 && col - 2 >= 0)
{
nextSquare = square - 6;
q.enque (nextSquare);
}
//downward moves
if (row + 2 <= 3 && col + 1 <= 3)
{
nextSquare = square + 9;
q.enque (nextSquare);
}
if (row + 2 <= 3 && col - 1 >= 0)
{
nextSquare = square + 7;
q.enque (nextSquare);
}
if (row + 1 <= 3 && col + 2 <= 3)
{
nextSquare = square + 6;
q.enque (nextSquare);
}
if (row + 1 <= 3 && col - 2 >= 0)
{
nextSquare = square + 2;
q.enque (nextSquare);
}
}
//complete this method.
void displayPath (int from, int to)
{
//ItemQue is a priority que that queus ItemType items.
//IntQue is a regular que that queues ints.
//It%u2019s used to store adjacent vertices.
ItemQue mq;
IntQue nextSquaresq;
ItemType item;
//The following variables are used to save values from an item dequed.
//The item dequeued is considered the parent item.
//These values are used
//to create next level items.
//
//We save the parent vertex number.
//We will use it to pass it to method edges ( )to find each of its
//child's distance from the parent vertex.
//We obtain this from the vertex path list stored in the parent item.
//It is stored as the last vertex in the path list.
//
//We save the parent path length.
//We will use this value to generate the path length of each child.
//The path list of each child will be one greater than the parent.
//
//We do not save the parent path. Because, every child
//vertex path has the same path as the parent vertex except that an
//additional vertex is added to the path.
int p_vertex; //parent vertex # (i.e. the vertex just dequeued).
int p_pathlen;//the length of the occupied part of the path array i.e.
//the length of path.
int nextSquarVertix; //a vertix
int marked [10]; //array to keep track of which vertices are marked.
//unmark all vertices.
for (int i=0;i<10;i++)
marked[i] = 0;
//prepare the first item to be queued.
//Initialize the path array to be all zeros.
for (int i=0;i<10;i++)
item.path[i] = 0;
//set the path of the start vertex to the start vertex to contain
//the start vertex.
item.path[0] = from; //first entry in the vertix array list.
//set the path length to be 1 because there is only one vertex in
//the path.
item.pathlen = 1;
//enque the item in the main item queue
//we enque this to get the algorithm started
//we will soon deque it and then enque its adjacents (i.e.children).
mq.enque (item);
//start the deque/enque loop
while ( ! (mq.isEmpty() ) )
{
//Deque the item.
mq.deque (item);
//break if target is reached.
if (item.path[item.pathlen-1] == to)
break;
//Save its values (call them parent values. These will be needed
//to generate (child) next level items
//For this purpose,
//Save the vertex number of this vertex. This vertex is the
//last vertex in the path list.
//Save the path length.
//We save them here because the variable item will be reused
//for preparing a next level item.
p_vertex = item.path[item.pathlen-1];
p_pathlen = item.pathlen;
//if the item is not yet marked. find the next level items.
if(marked[item.path[item.pathlen-1]] == 0 )
{
//mark the item
marked[item.path[item.pathlen-1]] = 1;
//Find the next level vertices. receive them in an int que
//Call method findAdj and pass it an int queue.
//findAdj method will return list of adjacent (child)
//vertices in the int queue passed to it.
getNextSquares (item.path[item.pathlen-1], nextSquaresq);
//enque next level items in the priority que
while ( !(nextSquaresq.isEmpty()) )
{
//deque a next level (i.e. child) vertex
//the vertix number of one of the next level vertices
// will be returned in an int vertex
nextSquaresq.deque (nextSquarVertix);
//if the next level vertix is not marked.
//Prepare an item for it and
//enque the item in the priority queue
//Use the same item variable as above.
//But modify it as below.
if (marked[nextSquarVertix] == 0)
{
//prepare an item for it by
//reusing the item variable.
//add the vertex to the path list in the item
item.path[p_pathlen] = nextSquarVertix;
//update the length of the used verix array list
item.pathlen = p_pathlen + 1;
//enque the item in the priority que
mq.enque (item);
}
}
}
}
//write code here to display the path from the start vertex to the target vertex.
}
int main()
{
int startSquare, targetSquare;
cout << "Enter start square" << endl;
cin >> startSquare;
while (startSquare>0 && startSquare<16){
cout << "Enter target square" << endl;
cin >> targetSquare;
//display the shortest path
displayPath (startSquare, targetSquare);
cout << "Enter start square" << endl;
cin >> startSquare;
}
return 0;
}
Explanation / Answer
#include <iostream>
using namespace std;
struct ItemType
{
int path [10];//An array containing a list of vertices along the path
//from the start vertex to this vertex.
int pathlen; //The length of the occupied part of the above array i.e.
//the length of the path stored in the above array.
};
struct Node
{
int path [10];//An array containing a list of vertices along the path
//from the start vertex to this vertex.
int pathlen; //The length of the occupied part of the above array i.e.
//the length of the path stored in the above array.
ItemType * link; //Link to the next item node.
};
//write these classes
class IntQue
{
private:
Node * head;
public:
bool isEmpty();
void enque (int n);
void deque(int & n);
};
class ItemQue
{
private:
Node * head;
public:
bool isEmpty();
void enque (ItemType item);
void deque(ItemType & item);
};
bool IntQue::isEmpty()
{
return false;
}
void IntQue::enque (int n)
{
}
void IntQue::deque(int & n)
{
}
bool ItemQue::isEmpty()
{
return false;
}
void ItemQue::enque (ItemType item)
{
}
void ItemQue::deque(ItemType & item)
{
}
void getNextSquares (int square, IntQue & q)
{
int nextSquare;
int row = square / 4;
int col = square % 4;
//upward moves
if (row - 2 >= 0 && col + 1 <= 3)
{
nextSquare = square - 7;
q.enque (nextSquare);
}
if (row - 2 >= 0 && col - 1 >= 0)
{
nextSquare = square - 9;
q.enque (nextSquare);
}
if (row - 1 >= 0 && col + 2 <= 3)
{
nextSquare = square - 2;
q.enque (nextSquare);
}
if (row - 1 >= 0 && col - 2 >= 0)
{
nextSquare = square - 6;
q.enque (nextSquare);
}
//downward moves
if (row + 2 <= 3 && col + 1 <= 3)
{
nextSquare = square + 9;
q.enque (nextSquare);
}
if (row + 2 <= 3 && col - 1 >= 0)
{
nextSquare = square + 7;
q.enque (nextSquare);
}
if (row + 1 <= 3 && col + 2 <= 3)
{
nextSquare = square + 6;
q.enque (nextSquare);
}
if (row + 1 <= 3 && col - 2 >= 0)
{
nextSquare = square + 2;
q.enque (nextSquare);
}
}
//complete this method.
void displayPath (int from, int to)
{
//ItemQue is a priority que that queus ItemType items.
//IntQue is a regular que that queues ints.
//It%u2019s used to store adjacent vertices.
ItemQue mq;
IntQue nextSquaresq;
ItemType item;
//The following variables are used to save values from an item dequed.
//The item dequeued is considered the parent item.
//These values are used
//to create next level items.
//
//We save the parent vertex number.
//We will use it to pass it to method edges ( )to find each of its
//child's distance from the parent vertex.
//We obtain this from the vertex path list stored in the parent item.
//It is stored as the last vertex in the path list.
//
//We save the parent path length.
//We will use this value to generate the path length of each child.
//The path list of each child will be one greater than the parent.
//
//We do not save the parent path. Because, every child
//vertex path has the same path as the parent vertex except that an
//additional vertex is added to the path.
int p_vertex; //parent vertex # (i.e. the vertex just dequeued).
int p_pathlen;//the length of the occupied part of the path array i.e.
//the length of path.
int nextSquarVertix; //a vertix
int marked [10]; //array to keep track of which vertices are marked.
//unmark all vertices.
for (int i=0;i<10;i++)
marked[i] = 0;
//prepare the first item to be queued.
//Initialize the path array to be all zeros.
for (int i=0;i<10;i++)
item.path[i] = 0;
//set the path of the start vertex to the start vertex to contain
//the start vertex.
item.path[0] = from; //first entry in the vertix array list.
//set the path length to be 1 because there is only one vertex in
//the path.
item.pathlen = 1;
//enque the item in the main item queue
//we enque this to get the algorithm started
//we will soon deque it and then enque its adjacents (i.e.children).
mq.enque (item);
//start the deque/enque loop
while ( ! (mq.isEmpty() ) )
{
//Deque the item.
mq.deque (item);
//break if target is reached.
if (item.path[item.pathlen-1] == to)
break;
//Save its values (call them parent values. These will be needed
//to generate (child) next level items
//For this purpose,
//Save the vertex number of this vertex. This vertex is the
//last vertex in the path list.
//Save the path length.
//We save them here because the variable item will be reused
//for preparing a next level item.
p_vertex = item.path[item.pathlen-1];
p_pathlen = item.pathlen;
//if the item is not yet marked. find the next level items.
if(marked[item.path[item.pathlen-1]] == 0 )
{
//mark the item
marked[item.path[item.pathlen-1]] = 1;
//Find the next level vertices. receive them in an int que
//Call method findAdj and pass it an int queue.
//findAdj method will return list of adjacent (child)
//vertices in the int queue passed to it.
getNextSquares (item.path[item.pathlen-1], nextSquaresq);
//enque next level items in the priority que
while ( !(nextSquaresq.isEmpty()) )
{
//deque a next level (i.e. child) vertex
//the vertix number of one of the next level vertices
// will be returned in an int vertex
nextSquaresq.deque (nextSquarVertix);
//if the next level vertix is not marked.
//Prepare an item for it and
//enque the item in the priority queue
//Use the same item variable as above.
//But modify it as below.
if (marked[nextSquarVertix] == 0)
{
//prepare an item for it by
//reusing the item variable.
//add the vertex to the path list in the item
item.path[p_pathlen] = nextSquarVertix;
//update the length of the used verix array list
item.pathlen = p_pathlen + 1;
//enque the item in the priority que
mq.enque (item);
}
}
}
}
//write code here to display the path from the start vertex to the target vertex.
}
int main()
{
int startSquare, targetSquare;
cout << "Enter start square" << endl;
cin >> startSquare;
while (startSquare>0 && startSquare<16){
cout << "Enter target square" << endl;
cin >> targetSquare;
//display the shortest path
displayPath (startSquare, targetSquare);
cout << "Enter start square" << endl;
cin >> startSquare;
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.