c++ - 理解 8 皇后拼图的对角搜索

Question

我正在解决8 queen问题并尝试通过互联网寻找比较解决方案，看看我的解决方案与其他解决方案相比如何。我发现了一个非常小的蛮力解决方案，这让我很困惑。我想知道是否有人愿意解释对角线比较实际上是如何工作的？

void solve(int n, int col, int *hist)
{
    int i;
    int j;

    if (col == n)
    {
        print_solution(n, hist);
    }
    i = 0;
    while (i < n)
    {
        j = 0;
        while (j < col && !(hist[j] == i || abs(hist[j] - i) == col - j))
            j++;
        if (j < col)
        {
            i++;
            continue;
        }
        hist[col] = i;
        solve(n, col + 1, hist);
        i++;
    }
}

void main(void)
{
    int hist[8];

    solve(8, 0, hist);
}

具体的代码我在可视化方面遇到问题是:

abs(hist[j] - i) == col - j)

据我了解，它会检查对角线，但我没有看到它。

Answer 1

由于第一个循环条件是 j < col ，该条件的右侧为正。 i对应于当前正在检查的行，并且 hist[j]是j上皇后的那一排第 - 列。因此，这会检查两个点 (hist[j], j) 是否和(i, col)通过检查水平和垂直距离是否相等，位于对角线上的“正斜杠”(/) 或“反斜杠”(\) 上。 abs就是让两种情况一次性检查完毕。