Question

Backtracking

Write a program in c++ that moves an asterisk ‘*’ in a grid of 10x10 cells. Your program should start with * on position (2,3) i.e. 3rd column of 2nd row. After printing the grid and ‘*’, your program will ask user if he wants to move the ‘*’ Up, Down, Left or Right. If user presses ‘U’, ‘D’, ‘L’ or ‘R’, your program will move the ‘*’ one position accordingly. If user presses ‘Q’, your program should terminate.

2- There should not be any Memory Leakage in your code.

3- Your code should be readable and properly commented and interface of your program should be user friendly.

Answer 1

// File Name: StackStar.h
#ifndef _STACKSTAR
#define _STACKSTAR

#include <iostream>
#include <string>
#define MAX 100
using namespace std;

// Defines a template type class Stack
class StackStar
{
private:
// To store data
char *backtrack;
// To point to top
int top;
// Function to return top value
int getCurrentTop()
{
return top;
}
// Function to change top value
void setCurrentTop(int s)
{
top = s;
}
public:
// Prototype of member functions
StackStar();
bool isEmpty();
bool push(char);
bool pop();
char peek();
void clean();
bool display();
};// End of class

// Default constructor to set stack top to -1
StackStar::StackStar()
{
backtrack = new char[MAX];
setCurrentTop(-1);
}// End of constructor

// Function to return true if stack is empty otherwise returns false
bool StackStar::isEmpty()
{
// Checks if top value is -1 then returns true otherwise returns false
return(top == -1);
}// End of function

// Function to push an item at the top of the stack
bool StackStar::push(char opt)
{
// Checks if stack top value is equals to 99, then return false (stack is full)
if (top == 99)
{
cout << "stack is full\n";
return false;
}// End of if condition

// Otherwise stack is not full
else
{
// Assigns parameter value to stack top position
// increase the stack top by one
backtrack[++top] = opt;

// returns true for successfully pushed data
return true;
}// End of else
}// End of function

// Function to pop an item from the top of the stack
bool StackStar::pop()
{
// Calls the function to check stack is empty then return false
if (isEmpty())
{
cout << "pop failed, stack is empty\n";
return false;
}// End of if condition

// Otherwise stack is not empty
else
{
// Decrease the top index value by one
top--;
// returns true for successfully popped item
return true;
}// End of else
}// End of function

// Function to return the stack top element
char StackStar::peek()
{
// Calls the function to check stack is empty then return false
if (isEmpty())
{
cout << "stack is empty program aborted \n";
exit(0);
}// End of if condition

// Otherwise stack is not empty
else
{
// Returns the stack top index position element
return backtrack[top];
}// End of else
}// End of function

// Function to delete all the element from the stack
void StackStar::clean()
{
// Calls the function to set stack top position to -1
setCurrentTop(-1);
}// End of function
#endif
---------------------------------------------------------------------------------------------------------------

// File Name: MoveStar.cpp
#include <iostream>
#include <cstdlib>
#include "StackStar.h"
#define MAXR 10 // Maximum number of rows for board
#define MAXC 10 // Maximum number of columns for board
using namespace std;

/**
* Function to move the star to one position up in the board
* Parameters:
* ss - Stack object to store the movement. Returns by reference
* board - Character type matrix to represent board data
* r - Current row index position
* c - Current column index position
* Return:
* Returns the updated row using pass by reference
*/
void moveUp(StackStar &ss, char board[][MAXC], int &r, int c)
{
// Checks if after subtracting one from the row it is equals to -1
// then display error message
if(r - 1 == -1)
cout<<"\n Cannot move up. At first row."<<endl;

// Otherwise valid position
else
{
// Assigns space to current row and column position of the matrix board
// to remove the '*'
board[r][c] = ' ';
// Decrease the row index by one and assigns '*'
board[--r][c] = '*';
// Pushes the operation to stack
ss.push('U');
}// End of else
}// End of function

/**
* Function to move the star to one position down in the board
* Parameters:
* ss - Stack object to store the movement. Returns by reference
* board - Character type matrix to represent board data
* r - Current row index position
* c - Current column index position
* Return:
* Returns the updated row using pass by reference
*/
void moveDown(StackStar &ss, char board[][MAXC], int &r, int c)
{
// Checks if after adding one to the row it is equals to maximum row
// then display error message
if(r + 1 == MAXR)
cout<<"\n Cannot move down. At last row."<<endl;

// Otherwise valid position
else
{
// Assigns space to current row and column position of the matrix board
// to remove the '*'
board[r][c] = ' ';
// Increase the row index by one and assigns '*'
board[++r][c] = '*';
// Pushes the operation to stack
ss.push('D');
}// End of else
}// End of function

/**
* Function to move the star to one position left in the board
* Parameters:
* ss - Stack object to store the movement. Returns by reference
* board - Character type matrix to represent board data
* r - Current row index position
* c - Current column index position
* Return:
* Returns the updated column using pass by reference
*/
void moveLeft(StackStar &ss, char board[][MAXC], int r, int &c)
{
// Checks if after subtracting one from the column it is equals to -1
// then display error message
if(c - 1 == -1)
cout<<"\n Cannot move left. At first column."<<endl;

// Otherwise valid position
else
{
// Assigns space to current row and column position of the matrix board
// to remove the '*'
board[r][c] = ' ';
// Decrease the column index by one and assigns '*'
board[r][--c] = '*';
// Pushes the operation to stack
ss.push('L');
}// End of else
}// End of function

/**
* Function to move the star to one position right in the board
* Parameters:
* ss - Stack object to store the movement. Returns by reference
* board - Character type matrix to represent board data
* r - Current row index position
* c - Current column index position
* Return:
* Returns the updated column using pass by reference
*/
void moveRight(StackStar &ss, char board[][MAXC], int &r, int &c)
{
// Checks if after adding one to the column it is equals to maximum column
// then display error message
if(c + 1 == MAXC)
cout<<"\n Cannot move right. At last column."<<endl;

// Otherwise valid position
else
{
// Assigns space to current row and column position of the matrix board
// to remove the '*'
board[r][c] = ' ';
// Increase the column index by one and assigns '*'
board[r][++c] = '*';
// Pushes the operation to stack
ss.push('R');
}// End of else
}// End of function

/**
* Function to undo move the star to one position up in the board
* Parameters:
* ss - Stack object to store the movement. Returns by reference
* board - Character type matrix to represent board data
* r - Current row index position
* c - Current column index position
* Return:
* Returns the updated row using pass by reference
*/
void undoMoveUp(char board[][MAXC], int &r, int c)
{
// Assigns space to current row and column position of the matrix board
// to remove the '*'
board[r][c] = ' ';
// Decrease the row index by one and assigns '*'
board[++r][c] = '*';
}// End of function

/**
* Function to undo move the star to one position down in the board
* Parameters:
* ss - Stack object to store the movement. Returns by reference
* board - Character type matrix to represent board data
* r - Current row index position
* c - Current column index position
* Return:
* Returns the updated row using pass by reference
*/
void undoMoveDown(char board[][MAXC], int &r, int c)
{
// Assigns space to current row and column position of the matrix board
// to remove the '*'
board[r][c] = ' ';
// Decrease the row index by one and assigns '*'
board[--r][c] = '*';
}// End of function

/**
* Function to undo move the star to one position left in the board
* Parameters:
* ss - Stack object to store the movement. Returns by reference
* board - Character type matrix to represent board data
* r - Current row index position
* c - Current column index position
* Return:
* Returns the updated column using pass by reference
*/
void undoMoveLeft(char board[][MAXC], int r, int &c)
{
// Assigns space to current row and column position of the matrix board
// to remove the '*'
board[r][c] = ' ';
// Increase the column index by one and assigns '*'
board[r][++c] = '*';
}// End of function

/**
* Function to undo move the star to one position right in the board
* Parameters:
* ss - Stack object to store the movement. Returns by reference
* board - Character type matrix to represent board data
* r - Current row index position
* c - Current column index position
* Return:
* Returns the updated column using pass by reference
*/
void undoMoveRight(char board[][MAXC], int &r, int &c)
{
// Assigns space to current row and column position of the matrix board
// to remove the '*'
board[r][c] = ' ';
// Decrease the column index by one and assigns '*'
board[r][--c] = '*';
}// End of function

// Function to display menu, accept user choice and returns user choice
char menu()
{
char choice;
cout<<"\n\n **************** Move Menu **************** ";
cout<<"\n U - UP \n D - Down \n L - Left \n R - Right \n Z - Undo \n Q - Quit \n\t What is your choice? ";
cin>>choice;
return choice;
}// End of function

// Function to assign space character to each cell of the board
void initBoard(char board[][MAXC])
{
// Loops till number of rows
for(int r = 0; r < MAXR; r++)
// Loops till number of columns
for(int c = 0; c < MAXC; c++)
// Assigns space character to current cell
board[r][c] = ' ';
}// End of function

// Function to display the board
void showBoard(char board[][MAXC])
{
// Loops till number of rows
for(int r = 0; r < MAXR; r++)
{
// Loops till number of twice the size of number of rows add 1
// to display row line
for(int l = 0; l < (MAXR * 2) + 1; l++)
cout<<"-";
cout<<endl;

// Loops till number of rows
for(int c = 0; c < MAXC; c++)
// Displays the current cell value
cout<<"|"<<board[r][c];
cout<<"|"<<endl;
}// End of for loop

// Loops till number of twice the size of number of rows add 1
// to display row line
for(int l = 0; l < (MAXR * 2) + 1; l++)
cout<<"-";
}// End of function

// main function definition
int main()
{
StackStar ss;
char undoOpt;
// Character array to represent board
char board[MAXR][MAXC];
// Initial row position
int r = 2;
// Initial column position
int c = 3;
// Calls the function to create the board
initBoard(board);

// Assigns '*' to current row and column index
board[r][c] = '*';

// Loops till user choice is not 'Q' or 'q'
do
{
// Call the function to display the board
showBoard(board);

// Calls the function to accept user choice
// Calls respective function based on returned user choice
switch(menu())
{
case 'U':
case 'u':
moveUp(ss, board, r, c);
break;
case 'D':
case 'd':
moveDown(ss, board, r, c);
break;
case 'L':
case 'l':
moveLeft(ss, board, r, c);
break;
case 'R':
case 'r':
moveRight(ss, board, r, c);
break;
case 'Z':
case 'z':
// Checks if stack is empty then display error message
if(ss.isEmpty())
cout<<"\n Nothing to undo.\n";

// Otherwise stack is not empty
else
{
// Extracts the stack top position operation
undoOpt = ss.peek();
// Removes the stack top position operation
ss.pop();

// Checks the operation and calls appropriate function
switch(undoOpt)
{
case 'U':
undoMoveUp(board, r, c);
break;
case 'D':
undoMoveDown(board, r, c);
break;
case 'L':
undoMoveLeft(board, r, c);
break;
case 'R':
undoMoveRight(board, r, c);
break;
}// End of inner switch - case
}// End of else
break;
case 'Q':
case 'q':
cout<<"\n\t Thanks.";
exit(0);
default:
cout<<"\n Invalid choice!!"<<endl;
}// End of switch - case
}while(1);// End of do - while loop
return 0;
}// End of main function

Sample Output:

---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | |*| | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? u
---------------------
| | | | | | | | | | |
---------------------
| | | |*| | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? u
---------------------
| | | |*| | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? u

Cannot move up. At first row.
---------------------
| | | |*| | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? z
---------------------
| | | | | | | | | | |
---------------------
| | | |*| | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? z
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | |*| | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? z

Nothing to undo.
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | |*| | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? r
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | |*| | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? r
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | |*| | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? r
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | |*| | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? d
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | |*| | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? d
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | |*| | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? z
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | |*| | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? z
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | |*| | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? z
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | |*| | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? z
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | |*| | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? z
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | |*| | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? z

Nothing to undo.
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | |*| | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | | | | |
---------------------

**************** Move Menu ****************
U - UP
D - Down
L - Left
R - Right
Z - Undo
Q - Quit
What is your choice? q

Thanks.