Question

Problem 5.2 [4 POINTS): Suppose you are writing a program to make a turtle walk through a maze. In order for the turtle to make the correct decisions, you must use backtracking to keep track of all the moves made before. What data structure would you use and why? If you do NOT explain/discuss the reason(s) why you choose the data structure, you will lose at least half credit.

Answer 1

This is an example of rat in a maze problem. This is solved by backtracking using the data structure stack. The assumption used is the turtle starts from the coordinates (0,0). A structure node is used which will have members, the x coordinate of the node, the y coordinate of the node, and a variable dir which will keep track of which directions we have tried and which direction to choose next. We will be trying all the directions in anti-clockwise starting from the direction up. Initially dir is assigned 0

• If dir = 0, try up.
• If dir=1 try left.
• If dir=2 try down
• If dir=3 try right

Else retract back to the previous block of the maze.

Initially, a node with indexes i=0, j=0 and dir=0 is pushed into the stack. Then, we move to all the direction of the topmost node one by one in an anti-clockwise manner and each time as we try out a new path that node is pushed in the stack. The dir variable of the topmost node will be increased each time so that we can try a new direction each time unless all the directions are explored ie. dir=4. If dir equals to 4 we will pop that node from the stack that means we are backtracking one step to the path where we came from. This trial and error method requires pushing and popping operation so that we can maintain the right path in the stack contents. The stack data structure allows us to do the desired operations hence it is used here.

Hope this helped. Please do upvote and if there are any queries please ask in comments section.