Help with understanding backtracking

[Bvwalker1]

Let’s say I have a tree structure and I’m starting at the root and I want to travel down each path to its final node. I get that a recursive function makes sense to do this, but how do you make sure that after you traverse a path and then back up a level or more to traverse another path, that you aren’t revisiting a previous path. Wouldn’t you need to keep track of where you have been already so you don’t re-visit the same path? Can someone help me understand how this works? Thanks!

 

[Skydiver]

It sounds more like you are asking about depth first searches, rather than backtracking.

Typically, before you go down a path, you have an ordered list of the possible paths too go down. You iterate over that list sequentially either by preloading a queue, or by looping and then recursion. When they execution state pops out of the recursion, it will pick up the next item in the queue, or the next item index in the loop.

 

[Bvwalker1]

It sounds more like you are asking about depth first searches, rather than backtracking.

Typically, before you go down a path, you have an ordered list of the possible paths too go down. You iterate over that list sequentially either by preloading a queue, or by looping and then recursion. When they execution state pops out of the recursion, it will pick up the next item in the queue, or the next item index in the loop. I’m going to do it in C#. I just started learning it, so I’m no means an expert.

Thanks for the information. What I’m actually trying to do is determine all the solutions to the peg puzzle that you see at Cracker Barrel. I will have a list of legal moves, and my idea was to start with a given position and then have program check all possible paths from that position keeping track of the ones that have a depth of 13 since there are 14 pegs and 15 holes and the object is to have one peg left. I know logically how I need to do it, I’m just not clear on the data structures needed. As I mentioned before, I could see where recursion would work to find a path, but it seems like I would need to keep track of the paths tried so they aren’t tried again.

 

[Skydiver]

Solve the problem first without pruning similar paths, or paths that are isomorphic.

 

[Skydiver]

As I mentioned before, I could see where recursion would work to find a path, but it seems like I would need to keep track of the paths tried so they aren’t tried again.

And you won't if you use a loop or queue to keep track of the edges. If you iterate over the edges sequentially, you won't go down that edge again.

Also, I am assuming that you were accurate in the beginning of this thread when you said that you had a tree. A tree contains no cycles. There is a graph theory theorem that starts that paths from any node to any other node in a tree will be unique. Therefore, as long as you don't go down the same edge again, you still never revisit the same path.

 

[Skydiver]

Also, while I am thinking about it, I thought that either Sedgwick's Algorithms and Data Structures book, or Knuth's (1st?) book that covers algorithms tackles that puzzle. All I recall now is skipping over the section because I had previously worked out the solution a year beforehand before I took the Algorithms and Data Structures course. Of course now, with my post-surgery anesthesia memory loss, I don't recall the fine details anymore, and I'll have to either work it out again from scratch, or flip through both books to find their solutions. All I recall at this point is I didn't tackle trying to solve the polymorphism problem, and neither did either author. It was only later while learning graph theory that I realized that some tricks could be applied to tackle the polymorphism and thereby reduce the search space.