2

任务是计算将 N 个皇后放在 NxN 板上的解决方案的数量。我试图考虑所有可能的情况来提高性能，但是在 N = 15 的情况下运行几乎需要 50 秒。这是我所做的：

Dim resultCount As Integer = 0
Dim fieldSize As Integer = 0
Dim queenCount As Integer = 0
Dim availableCols As Boolean()
Dim availableLeftDiagonal As Boolean()
Dim availableRightDiagonal As Boolean()

Private Sub butCalc_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles butCalc.Click
    Dim currentTime As Long = Now.Ticks

    'Reset old result
    resultCount = 0
    fieldSize = CInt(txtFieldSize.Text)
    queenCount = 0

    ReDim availableCols(fieldSize - 1)
    For i As Integer = 0 To fieldSize - 1
        availableCols(i) = True
    Next

    ReDim availableLeftDiagonal((fieldSize - 1) * 2)
    For i As Integer = 0 To (fieldSize - 1) * 2
        availableLeftDiagonal(i) = True
    Next

    ReDim availableRightDiagonal((fieldSize - 1) * 2)
    For i As Integer = 0 To (fieldSize - 1) * 2
        availableRightDiagonal(i) = True
    Next

    'Calculate
    For x As Integer = 0 To fieldSize - 1
        putQueen(x, 0)
    Next

    'Print result
    txtResult.Text = "Found " & resultCount & " in " & (Now.Ticks - currentTime) / 10000 & " miliseconds."
End Sub

Private Sub putQueen(ByVal pX As Integer, ByVal pY As Integer)
    'Put in result
    availableCols(pX) = False
    availableLeftDiagonal(pX + pY) = False
    availableRightDiagonal(pX - pY + (fieldSize - 1)) = False
    queenCount += 1

    'Recursion
    If (queenCount = fieldSize) Then
        resultCount += 1
    Else
        pY += 1 'pY = next row
        For x As Integer = 0 To fieldSize - 1
            If (availableCols(x) AndAlso
                availableLeftDiagonal(x + pY) AndAlso
                availableRightDiagonal(x - pY + (fieldSize - 1))) Then putQueen(x, pY)
        Next
        pY -= 1 'Reset pY
    End If

    'Roll up result
    availableCols(pX) = True
    availableLeftDiagonal(pX + pY) = True
    availableRightDiagonal(pX - pY + (fieldSize - 1)) = True
    queenCount -= 1
End Sub

请告诉我是否可能（我的老师没有给出确切的时间，他只是告诉“可接受的时间”。如果可能，请告诉我如何，或者只是给我一个线索！

4

3 回答 3

8

我会考虑以某种方式考虑到大多数解决方案只不过是其他解决方案的镜像或旋转版本。例如，您不需要尝试将第一个皇后放在从左到右的每一列中。如果你只从左到中，这可能就足够了。这已经将时间缩短了一半。如果我没记错的话，例如，对于 8x8 棋盘，将皇后放在第 7 列会产生与将其放在第 2 列相同的结果集，只是翻转了。为什么不呢？

解决指数复杂性问题：老实说，20x20 棋盘上的 20 个皇后创建了如此巨大的树，我认为没有任何优化能够在合理的时间内为您提供准确的结果。我刚刚查了一下，n=20 有近 400 亿个解。请参阅oeis.org/A000170 - n=20 的解决方案比 n=15 多约 17,000 倍。我不认为我们可以通过这个因素优化你的算法。因此，即使我们尽了最大努力，将 n=15 缩短到 2 秒……对于 n=20，这仍然意味着将近 10 个小时。

你也可以这样想。如果有 39 029 188 884 个 20x20 棋盘和 20 个皇后的解决方案，它有多少数据？要记住每个解，你需要存储从 1 到 20 的 20 个数字（水平位置，或者每个皇后的 x 坐标）。您需要 5 位来表示小于 20 的数字，因此每个解决方案需要 5*20 = 100 位。100 位乘以 39 029 188 884 表示 3634 GB。

这就是你的程序必须生成的数据量（我知道你不需要保存解决方案，你只是在数它们：但你需要生成它们中的每一个，这样你就可以勾选它）。你的老师不能合理地期望你编写一个程序，在心跳中生成 3634 GB 有意义的数据。

有一些方法可以估计这样的结果——例如一遍又一遍地随机分布皇后，并计算你碰巧让它们处于满足标准的位置的次数（它们都不会互相攻击）；例如，可能有 0.0013% 的时间。然后乘以(n*n)！/ (n*(n-1))! - 所有可能配置的数量，你得到一个估计。但这显然只是一个估计。你随意散布它们的时间越长，这个估计就越准确。

于 2011-08-20T12:56:33.123 回答
2

我已经完成了组合枚举，但没有专门进行 N 个皇后。这是我会尝试的（但正如莫拉夫斯基指出的那样，再次降低您的期望）。

  1. 替换availableCols为列出剩余列的数组。将对角线存储为位数组。如果有太多的单词无法放入一个单词中，那么单独处理仅包含前几行的对角线（即仅在树顶部附近相关的对角线）可能是值得的。理想情况下，测试一个新的女王只需要几个指令。如果 N 被积极优化的编译器知道，它会有所帮助。

  2. 使用可用的二面体对称性仅枚举每个轨道中字典顺序最少的解。通过不是 Burnside 的引理恢复总计数。对称性破坏的成本足够高，以至于什么时候做它是一门艺术，但有一些低垂的果实（例如，不要将女王放在上列的第一行）。按行放置可能不是最佳策略。

  3. 在搜索树的内部节点测试广义弧一致性。这对于家庭作业来说可能涉及太多了，但我确信在 OEIS 序列背后的真正高效计算中使用了类似的东西。

于 2011-08-20T17:30:25.393 回答
1

这通常在编程竞赛中完成的方式是将结果放入代码中的数组中，然后打印正确的结果。这真的很快，但可能不是你的老师想要的。再说一次，也许是。

于 2011-08-20T13:27:20.583 回答