Backtracking algorithm

Assignment Help Data Structure & Algorithms
Reference no: EM131369516

Assignment

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:

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.

Attachment:- MazeTest.txt

Verified Expert

In this assignment we need to find a way for mouse to reach from source to goal destination .This assignment was about backtracking in two dimensional array .given algorithm is not optimize we can use A* algorithm to solve this problem much faster.

Reference no: EM131369516

Questions Cloud

Computer is able to check the entire population of pencils : New computerized systems are able to check for defects on products right on the assembly line. For example: a pencil manufacturer is able to use laser scanning to check for the size of the pencils. Since the computer is able to check the entire popul..
Inventories and inventory management : Inventories - and inventory management - should be a thing of the past. An efficient and effective organization should be able to employ lean and just-in-time concepts so that inventories are not necessary. Do you agree or disagree with this statemen..
What organizing to implement vertical integration means : Please explain in detail what "Organizing to implement vertical integration" means and how it involves organizational structure, management controls and compensation policies.
Dictum of management theory : It has long been a dictum of management theory that leaders must adapt their behavior to fit the specifics of a situation. Discuss whether transformational leadership is appropriate for all occasions. In which situations might it not be effective and..
Backtracking algorithm : COSC 2007 -Data Structures - 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
What are difference between discrete and continuous variable : qnt 275-What are the differences between quantitative and qualitative variables? What are the differences between discrete and continuous variables.
What is the probability : Assume that 2% invest in both kinds. If an investor is chosen at random, what is the probability that this investor has either public or corporate funds?
What will be the price level of the overall economy : ECON 3123- Suppose that the economy consists of two types of firms. Flexible price firms, who set prices P + a(Y - Y¯), and sticky price firms, who set prices E(P). Fraction s of the firm population is sticky. What will be the price level of the o..
Probability that randomly chosen user could not use a device : If there were 18 million users of handheld data devices of this kind on that day, what is the probability that a randomly chosen user could not use a device?

Reviews

inf1369516

2/6/2017 5:27:17 AM

Sorry for last email. You have a great job, I was simply getting somewhat stressed. Why I have no clue! This is effectively my fifth or sixth paper from all of you and they have been only extraordinary. This proposition is great done. Expert did awesome.

inf1369516

2/6/2017 5:26:13 AM

Could you please make a discount for me? I have done many orders with you, and also I have more assignments this semester I will order from you guys. I would like to ask you about the output, it seems to me in each step the position is not changing , is it correct output , or it has to be changing in each step ? Also, please make a full comments for the program to understand the code, last thing, Did you use The backtracking algorithm that provided in the question file ? thank you..

len1369516

1/24/2017 3:34:07 AM

a basic java program that should be using a stack class all details is in the file attached In this question, you will test, using a backtracking algorithm, if a mouse can escape from a rectangular maze. 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).

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Investment strategy your knowledge of algorithms

Planning an investment strategy your knowledge of algorithms helps you obtain an exciting job with the acme computer company, along with a $10,000 signing bonus. you decide to invest this money with the goal of maximizing your return at the end of..

  Part-1greatest common divisor show a recursive

part-1greatest common divisor show a recursive implementation of euclids algorithm for finding the greatest common

  Write advantage of linked list implementation of stack

The tree's item type is int. Function must return number of leaves in tree. Determine the advantage of linked list implementation of stack versus array implementation?

  The lims to support multiple clients to query and update

the lims to support multiple clients to query and update the library inventory using a clientserver model. lims

  Studying in major paralegal

Make a Microsoft Word document which includes a table and hyperlinks to Web sites helpful to someone studying in your main Paralegal.

  Identify the three sublists that exist at that point

An array contains the elements shown below. Using a quick sort, show the contents of the array after the first pivot has been placed in its correct location. Identify the three sublists that exist at that point.

  Input a list of employee names and salaries and determine

input a list of employee names and salaries and determine the meanaverage salary as well as the number of salaries

  Implementing one to one relationships

Explain the different ways of implementing one to one relationships. Suppose you are maintaining information on offices and faculty.

  Data systems and design

Suppose if you have a program with a housekeep() module, a mainloop() module, and a finishup() module, when is the second input record usually read?

  Create a table that depicts the runtime for arrays

Create a table that depicts the runtime for arrays of length 1 to 10. Would you expect the general runtime to be O(n), O(n2), O(n3), or some other function of n? Explain.

  Implement a virtual memory simulator based on demand paging

Will simulate the step by step execution of the OPT algorithm using the stored reference string; if there is no reference string stored yet, an error message must be displayed.

  Find the numberofstudentsin a computer algorithm course

This program will find the numberofstudentsin a computer algorithm course.The program will ask user to 6 integers. The design step will use both flowchart and pseudocode for better understanding.

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