432,086 Members | 1,875 Online
Need help? Post your question and get tips & solutions from a community of 432,086 IT Pros & Developers. It's quick & easy.

# Backtracking Recursion Problem

12 Replies

 P: n/a On Feb 15, 8:57 am, "NOO Recursion"

 P: n/a NOO Recursion wrote: Hi everyone! I am trying to write a program that will search a 12x12 for a thing called a "blob". A blob in the grid is made up of asterisks. A blob contains at least one asterisk. If an asterisk is in a blob, an asterisk that is contiguous to it is in the same blob. If a blob has more than two asterisks, then each asterisk in the blob is contiguous to at least one other asterisk in the blob. For example this 12x12 grid has 6 blobs. I am having a heck of a time trying to figure out how to do this with recursion. I have looked online for examples but all I have found close is maze problems. The language I am using is C++ and the compiler is Dev C++ 4.9.9.2. Any help would be greatly appreciated for I seem to be lost on this whole recursive thing. Recursion is easy once you get the hang of it. Here's some psuedo-code find_blob(x, y, blob) { if (in_grid(x, y) && grid[x][y] == '*' && !in_blob(blob, x, y)) { add_to_blob(blob, x, y); find_blob(x + 1, y, blob); find_blob(x - 1, y, blob); find_blob(x, y + 1, blob); find_blob(x, y - 1, blob); } } That's all there is to it. x and y are your cordinates, blob is some sort of data structure where you store the x and y coordinates that form a blob. add_to_blob adds a pair of coordinate to the blob, in_blob checks if a pair of x and y coordinates are already in a blob (so you don't add the same coordinates twice and get into an inifinite loop). Finally in_grid checks if x and y are inside the grid, so you don't fall over the edge of the grid. Easy (but untested). As you've been told this may not be the most efficient method, but I guess the purpose of the exercise is to learn recursion. Try coding up the pseudo-code above and come back if you have any problems. john Feb 15 '07 #4

 P: n/a Incidentally the above code involves recursion but no backtracking. I'm not sure where you got the idea that backtracking is necessary. Feb 15 '07 #5

 P: n/a John Harrison wrote: > Incidentally the above code involves recursion but no backtracking. I'm not sure where you got the idea that backtracking is necessary. Most likely from the homework assignment. However, he did post his code and his specific problem. Feb 15 '07 #6

 P: n/a Thanks everyone! I will take a look at all your post after work today. I will get back to you sometime tommorrow to tell you how it went. Thanks again! Feb 15 '07 #7

 P: n/a NOO Recursion wrote: ... I am having a heck of a time trying to figure out how to do this with recursion. ... There's a terminological issue here that needs to be resolved first: what exactly do you mean by "recursion" here? If you specifically need a C++ program that will simply contain a function that calls itself, then you are talking about mere "syntactical" recursion. It is rather strange to see a _requirement_ to use this kind of recursion anywhere besides a homework assignment, because in practical real-life cases it might be a good idea to avoid syntactical recursion in solving problems like that. If you are talking about algorithmic recursion (i.e. "recursion" as a particular flavor of divide-and-conquer approach in algorithm design), then it is a different story. This problem can indeed be easily solved by a D&C algorithm, but frankly, I don't see the actual need for the _recursive_ variety of D&C. There's no need to force the depth-first traversal and there's no need for backtracking (why are you mentioning it in the subject?), which normally means that there's no need for recursive D&C. So, what exactly do you mean by "recursion" anyway? -- Best regards, Andrey Tarasevich Feb 16 '07 #8

 P: n/a I am writing up my recursive solution to the problem. Thanks everyone you have all helped a lot. Ohh, and John thanks I am looking into your psuedo-code as a starting point for my solution. Seriously it has helped me figure out were to start on this. I will post my code when I am done. Thanks again. "John Harrison" Hi everyone! I am trying to write a program that will search a 12x12for a thing called a "blob". A blob in the grid is made up of asterisks.A blob contains at least one asterisk. If an asterisk is in a blob, anasterisk that is contiguous to it is in the same blob. If a blob hasmore than two asterisks, then each asterisk in the blob is contiguous toat least one other asterisk in the blob. For example this 12x12 grid has6 blobs. I am having a heck of a time trying to figure out how to dothis with recursion. I have looked online for examples but all I havefound close is maze problems. The language I am using is C++ and thecompiler is Dev C++ 4.9.9.2. Any help would be greatly appreciated for Iseem to be lost on this whole recursive thing. Recursion is easy once you get the hang of it. Here's some psuedo-code find_blob(x, y, blob) { if (in_grid(x, y) && grid[x][y] == '*' && !in_blob(blob, x, y)) { add_to_blob(blob, x, y); find_blob(x + 1, y, blob); find_blob(x - 1, y, blob); find_blob(x, y + 1, blob); find_blob(x, y - 1, blob); } } That's all there is to it. x and y are your cordinates, blob is some sort of data structure where you store the x and y coordinates that form a blob. add_to_blob adds a pair of coordinate to the blob, in_blob checks if a pair of x and y coordinates are already in a blob (so you don't add the same coordinates twice and get into an inifinite loop). Finally in_grid checks if x and y are inside the grid, so you don't fall over the edge of the grid. Easy (but untested). As you've been told this may not be the most efficient method, but I guess the purpose of the exercise is to learn recursion. Try coding up the pseudo-code above and come back if you have any problems. john Feb 20 '07 #9