1) Create a 5x5 matrix in C++ 2) The matrix is initialized to all 0\'s showing n
ID: 3872018 • Letter: 1
Question
1) Create a 5x5 matrix in C++
2) The matrix is initialized to all 0's showing no traversal yet.
3) Cur_Row and Cur_Col as 2 integer values representing the location of the Knight. Depending on where you start it might be 3 3 or 5 5 or 1 1 or 8 8.
4) Cur_Move is the current move number starting at 1 and being incremented each move.
5) There are 8 possible moves from the current location but not all are valid but must be considered.
Cur_Row=+2 Cur_Col=+1
Cur_Row=+2 Cur_Col=-1
Cur_Row=-2 Cur_Col=+1
Cur_Row=-2 Cur_Col=-1
Cur_Row=+1 Cur_Col=+2
Cur_Row=+1 Cur_Col=-2
Cur_Row=-1 Cur_Col=+2
Cur_Row=-1 Cur_Col=-2
6) Each valid move place the value of Cur_Move in the matrix at Cur_Row, Cur_Col and increment Cur_Move
7) The search space could be a tree or stack just like in the water jug problem. Only nodes are expanded in the tree if the value of Cur_Row and Cur_Col are less than the value of the max size of the matrix and the value at the location is 0 (unvisited).
For a 5x5 here are 2 solutions with the order of locations visited listed
1) starting location in the middle at 3 3
3 3, 1 4, 2 2, 4 1, 5 3, 4 5, 2 4, 1 2, 3 1, 5 2, 4 4, 2 5, 1 3, 2 1, 4 2, 5 4, 3 5, 2 3, 1 5, 3 4, 5 5, 4 3, 5 1, 3 2, 1 1
2) starting at bottom corner 5 5
5 5, 3 4, 1 5, 2 3, 1 1, 3 2, 5 1, 4 3, 3 5, 1 4, 2 2, 4 1, 3 3, 5 4, 4 2, 2 1, 1 3, 2 5, 4 4, 5 2, 3 1, 1 2, 2 4, 4 5, 5 3
Write a program using this representation to perform the knight’s tour. The result should be the matrix with the values showing the move that the square was visited. There might be other valid solutions but I know this one is valid. Define the search of the space and how to handle backtracking.
The output matrix for case 1 is:
25 8 13 2 19
14 3 18 7 12
9 24 1 20 17
4 15 22 11 6
23 10 5 16 21
Explanation / Answer
//
// KnightsTour.cpp
#include <iostream>
#include <utility>
#include <vector>
#include <stack>
struct matrix{
private:
//5x5 matrix data initialized with all zero
static const int size = 5;
int _m[size][size] = {0};
int Cur_Row;
int Cur_Col;
int Cur_Move = 0;
public:
matrix(int cur_row, int cur_col) : Cur_Row(cur_row), Cur_Col(cur_col){
move(cur_row, cur_col);
}
bool move(int toRow, int toCol){
//check if Range is valid
if((toRow <= 0) || (toRow > size) ) return false;
if((toCol <= 0) || (toCol > size)) return false;
//check if space is available
if(_m[toRow-1][toCol-1]!=0) return false;
++Cur_Move;
_m[toRow-1][toCol-1] = Cur_Move;
Cur_Row = toRow;
Cur_Col = toCol;
return true;
}
//check if Matrix has been totally traversed
bool isfull(){
return (size*size == Cur_Move);
}
//get current Row and Column
int getCurrentRow(){
return Cur_Row;
}
int getCurrentCol(){
return Cur_Col;
}
void print(){
for(int i = 0; i < size; ++i){
for(int j = 0; j < size; ++j){
std::cout << _m[i][j] << " ";
}
std::cout << std::endl;
}
}
};
struct KnightsTour{
public:
KnightsTour(){
}
/*
BackTracking is Along the lines of Depth First Search.
We Start from a given position and look for Next Position
corresponding to Knight's movement. All eight positins are possible,
except for (a) when they do not cross boundary, (b) when they
are not already occuppied
cur_row and cur_col corresponds to position from which BackTrack
is to be done.
*/
void backTrack(int cur_row, int cur_col){
static int NextMovements [8][2] = {
{2, 1},
{2, -1},
{-2, 1},
{-2, -1},
{1, 2},
{1, -2},
{-1, 2},
{-1, -2}
};
// a stack comprising of matrices
// this is Depth First Search
std::stack<matrix> smatrices;
smatrices.push(matrix(cur_row, cur_col));
while(!smatrices.empty()){
//get the next matrix
auto mat = smatrices.top();
smatrices.pop();
if(mat.isfull()){
mat.print();
std::cout << std::endl;
continue;
}
for(int i = 7; i >=0; --i){
matrix temp = mat;
int x = temp.getCurrentRow() + NextMovements[i][0];
int y = temp.getCurrentCol()+ NextMovements[i][1];
if(temp.move(x, y)){
smatrices.push(temp);
}
}
}
}
};
//checks movement corresponding to example given in question
void checkMovement(){
matrix m(3,3);
std::vector<std::pair<int,int>> movements = {
{3, 3}, {1, 4}, {2, 2}, {4, 1}, {5, 3},
{4, 5}, {2, 4}, {1, 2}, {3, 1}, {5, 2},
{4, 4}, {2, 5}, {1, 3}, {2, 1}, {4, 2},
{5, 4}, {3, 5}, {2, 3}, {1, 5}, {3, 4},
{5, 5}, {4, 3}, {5, 1}, {3, 2}, {1, 1}
};
for(auto movement: movements){
m.move(movement.first, movement.second);
}
m.print();
}
int main(){
KnightsTour kt;
//start backtracking
std::cout << " BackTracking for Start Position (3,3)";
kt.backTrack(3,3);
std::cout << " BackTracking for Start Position (5,5)";
kt.backTrack(5,5);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.