maze solver

This is a discussion on maze solver within the C++ Programming forums, part of the General Programming Boards category; Is it possible to solve the maze problem using Depth first search implemented using a stack. I think it's impossible. ...

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    50

    maze solver

    Is it possible to solve the maze problem using Depth first search implemented using a stack.

    I think it's impossible. because with the stack implementation you cannot backtrack.

    If you use the recursive implementation of Depth first search you can backtrack.

    Any idea's ?

  2. #2
    Registered User NeonBlack's Avatar
    Join Date
    Nov 2007
    Posts
    435
    You can't backtrack using a stack? How do you think recursion works?
    I copied it from the last program in which I passed a parameter, which would have been pre-1989 I guess. - esbo

  3. #3
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    thanks neoblack. Now in the recursive implementation of depth first search how do i print only the successfull path through the maze?

    Please help.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    NeonBlack is correct. Whatever can be done through recursion can always be done through maintaining an explicit stack.
    However, it is always much clearer to just use recursion.

    If you maintain an explicit stack then the successful path should exactly match the contents of the stack at the point you find the exit.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    Oh okay i'll try my best to solve this.
    Last edited by iamnew; 04-28-2010 at 02:36 AM.

  6. #6
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Of course it's possible. But solving a maze through breadth first search is a LOT better in my opinion.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Shortest Path Maze Solver (Breadth Search Help)
    By Raskalnikov in forum C Programming
    Replies: 5
    Last Post: 04-07-2009, 07:41 PM
  2. Recursive Stack Algorithm Maze Solver
    By unrestricted in forum C Programming
    Replies: 0
    Last Post: 09-04-2007, 03:11 AM
  3. CHeck my Maze Solver
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 07-31-2003, 10:37 PM
  4. Q: Recursion to find all paths of a maze
    By reti in forum C Programming
    Replies: 7
    Last Post: 11-26-2002, 08:28 AM
  5. My Maze Game --- A Few Questions
    By TechWins in forum Game Programming
    Replies: 18
    Last Post: 04-24-2002, 11:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21