J q data:不理解伪码:(Q[i]=j+r− i)或(Q[i]=j− r+i)-边看边学

我正在阅读 Jeff Erickson 的算法书“算法”（第一版）。

书在：https://github.com/jeffgerickson/algorithms/blob//1st%20edition/Algorithms-JeffE.pdf

在图 2.2 有伪代码：

PlaceQueens(Q[1 .. n], r):
    if r = n + 1
        print Q[1 .. n]
    else
        for j ← 1 to n
            legal ← True
            for i ← 1 to r − 1
                if (Q[i] = j) or (Q[i] = j + r − i) or (Q[i] = j − r + i)
                    legal ← False
            if legal
                Q[r] ← j
                PlaceQueens(Q[1 .. n], r + 1)    〈〈 Recursion! 〉〉

我知道（或猜测）“（Q [i] = j + r-i）或（Q [i] = j-r + i）”用于判断它是否在对角线上。

但是我不知道如何得到 Q [i] = j + r-i 和 Q [i] = j-r + i。

我可以使用斜率得到 Q [i] = j + r-i（或 Q [i] = j-r + i）关系？

有人帮忙吗？

Q[i] indicates which square in row i contains a queen.

所以我们需要检查，对于每一行，如果行“向上和向左”和“向上和向右”包含皇后。

j是我们试图放置女王的位置（不能保证它是合法的）。

r是我们到目前为止放置的当前皇后数量（r = 我们当前的皇后行）。

i是我们的迭代器，它遍历每个现有的 queen 行，并检查我们的新 queen 是否合法。请注意，只有这一点因我们尝试的每个位置而异。

因此，每次我们想要计算与当前皇后对角的值，并查看另一个皇后是否在该列中。

Q [i] = j r-i 表示查看第 i 行（1 到皇后数）。检查该皇后是否在通过采用新皇后的位置（j）并添加（r-i）表示的列中，这是我们需要采取的“向右”步数。例如，如果我们要添加四号皇后，我们将通过增加三号和三号来检查第一行中的对角皇后。

然后，我们做同样的事情，但在相反的垂直方向（左上），通过采取我们的新女王的位置（j）和减去（r + i）。

我建议把这个算法画在纸上。一个接一个地添加每个女王，并跟踪算法每一步的所有数字。这应该使算法清晰。

Q = [1, 3]
[
.Q..
...Q
]
say j = 2, r = 2
Trying to add here:
[
.Q..
...Q
..?.
]
i = 0:
  Q[0] == j + r − i -> 2 + 2 - 0 = 4 FALSE
  Q[0] == j - r + i -> 2 - 2 + 0 = 0 FALSE
i = 1
  Q[1] == j + r - i -> 2 + 2 - 1 = 3 TRUE (Q[1] is 3)
This makes sense (there is a Q diagonal to the proposed "?" spot in the image above.

本站系公益性非盈利分享网址，本文来自用户投稿，不代表边看边学立场，如若转载，请注明出处