Using a backtracking algorithm

Assignment Help Data Structure & Algorithms
Reference no: EM13316104

In this question, you will test, using a backtracking algorithm, if a mouse can escape from a rectangular maze. The backtracking algorithm helps the mouse by systematically trying all the routes through the maze until it either finds the exit or exhausts all possible routes (and concludes that the mouse is trapped in the maze). If the backtracking algorithm finds a dead end, it retraces its path until it reaches a position from which there is an untried path. The backtracking algorithm always tries all directions from any position, and always in the same order.

The input to the algorithm is a maze with walls (represented by '1' characters) and open passage ways (represented by '0' characters). The starting position of the mouse is represented by 'm' and the exit from the maze by 'e'. Your program should read the maze in from a file, and the name of the file should be a command-line argument. The first line of the input will contain the number of rows and the number of columns in a maze. Thus, the input might look like the following:

6 5
1 1 1 1 1
1 0 0 e 1
1 1 1 0 1
1 m 1 0 1
1 0 0 0 1
1 1 1 1 1
     
The maze will always have a wall around the outside, so you need not be concerned about the mouse falling off the maze as it explores all directions.  The backtracking algorithm keeps a stack of positions that are the beginnings of paths it has yet to try. From the current position, the algorithm pushes onto the stack any untried open neighboring positions (if there are any), always looking forward, backward, left and right from the current position. At each step, the algorithm pops the top position off the stack and pushes the untried neighboring positions onto the stack. The algorithm must mark each visited position with a period to avoid revisiting positions --- so that it will not
loop forever trying the same routes.

The backtracking algorithm works as follows:

read in the maze;

initialize the stack;

goalCell = the position of the exit in the maze;

startCell = the initial position of the mouse in the maze;

currentCell = startCell;

while currentCell is not the goalCell

  mark currentCell as visited;

push onto the stack the unvisited open neighbours of currentCell;

  if the stack is empty

    the mouse is trapped: we tried all routes and failed to find the

exit;

else

pop a cell from the stack and make it currentCell;

end while;

the mouse can escape the maze: we reached the goal cell.
    
Because the backtracking algorithm needs a stack, you should implement a stack class (or you can use that from COSC 2006). Each item in the stack is the position of a cell in the maze --- that is, the row and column number of the cell.  Your program should print out the maze after each cell is visited, showing which cells have already been visited. Finally, your program must print out a message indicating whether the exit was found or that no route to the exit could be found (the mouse is trapped).

To develop your program, you can use the input file testMaze.txt, which contains the above maze.

Reference no: EM13316104

Questions Cloud

What is the opportunity cost of taking this trip : You plan a major adventure trip for the summer. You won’t be able to take your usual summer job that pays $6,000, and you won’t be able to live at home for free. The cost of your travel
How do you think the higher demand has affected : How do you think the higher demand has affected the equilibrium wage? In which direction do you think the labor supply and demand shifted? Explain your reasoning.
What input current and voltage are needed : A step-up transformer has 24 turns on the primary coil and 780 turns on the secondary coil. what input current and voltage are needed
Which piece of information is more important in the utility : Which piece of information is more important in the utility maximization process: marginal utility per unit of the good or marginal utility per dollar? WHY?
Using a backtracking algorithm : If the backtracking algorithm finds a dead end, it retraces its path until it reaches a position from which there is an untried path. The backtracking algorithm always tries all directions from any position, and always in the same order.
Should it raise prices or lower prices explain : Suppose a pizza parlor is interested in increasing total revenue by adjusting its price. Should it raise prices or lower prices? Explain giving concrete examples.
What could be the main motives for marriott : Identify several major categories of segmentation used by Marriott. For each relate specific examples of hotel services tailored to various target n www.marriott.com offers a brief description of 13 brands of various Marriott hotels catering differ..
Find how long does it take for the grinding wheel to stop : An electric motor rotating a workshop grinding wheel at a rate of 9.80x10^1 rev/min is switched off. how long does it take for the grinding wheel to stop
A demand and supply curve for tickets to the celine dion : Suppose Blanca would prefer a certain income of $20,000 to the expected value of the gamble. Explain her preference toward risk by drawing a graph.

Reviews

Write a Review

Data Structure & Algorithms Questions & Answers

  Implement an open hash table

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

  Use a search tree to find the solution

Explain how will use a search tree to find the solution.

  How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

  Recursive tree algorithms

Write a recursive function to determine if a binary tree is a binary search tree.

  Determine the mean salary as well as the number of salaries

Determine the mean salary as well as the number of salaries.

  Currency conversion development

Currency Conversion Development

  Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote

  Design a gui and implement tic tac toe game in java

Design a GUI and implement Tic Tac Toe game in java

  Recursive implementation of euclids algorithm

Write a recursive implementation of Euclid's algorithm for finding the greatest common divisor (GCD) of two integers

  Data structures for a single algorithm

Data structures for a single algorithm

  Write the selection sort algorithm

Write the selection sort algorithm

  Design of sample and hold amplifiers for 100 msps by using n

The report is divided into four main parts. The introduction about sample, hold amplifier and design, bootstrap switch design followed by simulation results.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd