I am having trouble following why after completing the for loop with no placement, the program automatically decreases n by one and tries again. I've noted the section I am confused about with asterisks.
Trying to understand what it's doing, I tried it for 4 queens, and added a System.out.println(q[n]) and System.out.println(n) in the enumerate method. What it told me was that n starts at 0, it places q = 0, and sets n = 1 (everything's okay so far). It then sets q = 2, and n =2. However, it tries n = 2 four times (as specified in the loop), and it doesn't check out, and then it sets n = 1. This is where I am confused. I understand why it would want to do so (as q =2 apparently is not a good final placement), but I don't understand where in the code it tells it to decrease the n and try other permutations? Thanks for your help.
Also, how does it know not to try the same placements, like q = 2 again, and not get stuck in a loop?
Last question first: why *would* it try the same combination again? In other words, play computer for a little bit: run it "by hand", writing down the conditions and the steps being taken. Pay particular attention to when the recursion happens, and when it returns.
Subject question next: because you told it to!
First sentence last: the program doesn't decrease n at all, anywhere. The value of n only increases--the trick is to understand why you're seeing lower values sometimes. It's not because n has decreased in value... it's because you're looking at an old value of n.
It's really not all that difficult, but can sometimes take some mental effort to get over the initial confusion... hopefully those hints are enough to get you on the right track.
Joined: Jun 05, 2009
My understanding of recursion must be flawed; what I thought would happen was this:
Let's say we do it for a 4x4 board. It calls on enumerate (the second one) the first time, inputting an int array, all null, of length 4, int n = 0. N is set to 4, n != N so it continues on to the for loop, at which point it sets q = 0, which passes isconsistent, and therefore it calls upon enumerate again with the 0th element of the array equal to zero, and n = 1. Again, it gets to the for loop, sets q to both i = 0 and i = 1, and finally i = 2 because isconsistent didn't check out for either i=0 or i=1. Calls upon enumerate with inputs int array q and n+1=2, and gets to the for loop again. Tries i=0, i=1, i=2, i=3, all of which don't pass isconsistent, and then (here's where I'm confused), I thought the method would terminate? The for loop would end, having reached i<4, and then the method...? But I'm obviously missing something here.
Unless...it branches off? When it runs n=1 it sets q = 2, and enumerates with it, but instead of ending the for loop it also tries for 3 as well and then enumerates for that as well...? I don't know, I'm grasping at straws now.
The method *does* terminate--but your program doesn't just stop running, it continues from where the method was called. Over and over. Until the *original* loop terminates.
Seriously--do it by hand, on paper--we're not just telling you that for fun. It's a valuable exercise, and will most likely clear up your confusion. You're making a set of *nested* calls--when each call terminates it returns back to where it was before the call and *keeps on going*.
subject: Why does this recursion try each permutation?