recursion - 校验和识别 N-Queen 的解

Question

我已经通过使用回溯算法解决了 N-Queen 问题，并且可以在 C# 中生成所有独特且不同的解决方案。虽然，我已经通过在每一行中找到有效位置来限制递归级别，但对于 N > 15，该算法将非常缓慢。我怀疑原因是每个新解决方案我必须生成所有 8 个对称对应项并检查这个与已经找到了解决方案。如果这些都不包括在内，则可以将新解决方案添加到唯一解决方案中。

我在某处看到一个提示，将校验和附加到每个解决方案并创建一个字典，其中校验和将是关键，解决方案是列表。我找不到这篇文章，否则对校验和的概念来说是非常新的。

对此问题的任何帮助将不胜感激。

Answer 1

N皇后的散列或校验和生成？几点：

1. 皇后之间是等价的。这意味着我们不想连续乘以校验和的皇后项来区分它们，因为它们应该是等价的。

2. 立场是最重要的。

因此，我们可以从以下内容开始：

public int hashSolution (Queen[] queens) {
    int h = 0;
    for (Queen q : queens) {
        int queenHash = (q.getX() * 23) + q.getY();     // 23 is a prime.
        h += queenHash;
    }
    return h;
}