jeffgerickson
confused with Figure 2.2, ask for help.
When I read pseudocode of Figure 2.2，I am confused with the pseudocode:
if (Q[i] = j) or (Q[i] = j + r − i) or (Q[i] = j − r + i)
I know "Q[i] = j + r − i) or (Q[i] = j − r + i " is used to judge whether it is on the diagonal line. But I don't know how to get Q[i] = j + r − i and Q[i] = j − r + i . Anyone help?
In the inner loop, we're considering whether it's legal to place a queen at the row, column coordinates (r, j). Also, we're referring to a queen placed in some previous row i and column Q[i]; in other words, the previous queen was placed at (i, Q[i]). Since we want to avoid the diagonal, there are two cases to consider: when a previous queen is up and to the right, or when it is up and to the left.
Consider when the previous queen is in line of sight diagonally up and to the right. That means that, for some integer x, we have:
(r-x, j+x) = (i, Q[i])
Decomposing the pair as equations, this means:
r-x = i AND j+x = Q[i]
We can solve both equations for x and substitute to get a single equation:
r-i = x AND x = Q[i]-j
r-i = Q[i]-j
r-i+j = Q[i]
Rearranging terms, we get Q[i] = j+r-i. Now you can reason similarly for the other case, when the previous queen is up and to the left.
As you said:
for some integer x, we have:
(r-x, j+x) = (i, Q[i])
I don't understand that what does"some integer x" and "how to get (r-x, j+x) = (i, Q[i])" mean. Please explain in detail.
If you are standing at the square (r,j) and you move diagonally up and to the right by only one diagonal distance, that means you are moving up one row and to the right one column. In other words, you move to (r-1, j+1). Then you can repeat that several more times. If you move diagonally by x units, then you are moving to square (r-x, j+x). And if the previously-placed queen is already located at any of those places where you can move to, then that means there is some value for x so that (r-x, j+x) = (i, Q[i]).