"把N皇后",可以在N = 20的可接受时间内运行吗？

Question

任务是计算将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

请告诉我是否有可能(我的老师没有给出确切的时间,他只是告诉"可接受的时间".如果有可能,请告诉我如何,或者只是给我一个线索!

Answer 1

我想到某种方式考虑到大多数解决方案只不过是其他解决方案的镜像或旋转版本.例如,您不需要尝试将每个列中的第一个皇后从左到右放置.如果你只从左到中,那就足够了.这已经把时间缩短了一半.如果我没有弄错的话,那么对于一个8x8的电路板,例如,将女王放在第7列将会产生与将其放入第2列相同的结果集,只会翻转.为什么不呢？

解决指数复杂性问题:说实话,20x20电路板上的20个皇后会创建如此庞大的树,我认为没有任何优化能够在合理的时间内为您提供精确的结果.我只是查了一下,那里有近40个bilions解决方案,n = 20.参见oeis.org/A000170 - n = 20的解决方案比n = 15多大约1.7万.我不认为我们可以通过这个因素优化你的算法.因此,即使我们做到了最好,并且在n = 15时也只需要2秒......但是对于n = 20,它仍然意味着近10个小时.

你也可以这样思考.如果有20个20x20板和20个皇后的39 029 188 884解决方案,它有多少数据？要记住每个解决方案,您需要存储从1到20的20个数字(水平位置或每个女王的x坐标).您需要5位来表示数字<20,因此每个解决方案需要5*20 = 100位.100位乘以39 029 188 884意味着3634千兆字节.

这就是你的程序必须生成的数据量(我知道你不需要保存解决方案,你只是计算它们:但是你需要生成它们中的每一个以便你可以勾选它).您的老师无法合理地期望您编写一个程序,在心跳中生成3634千兆字节的有意义数据.

有一些方法可以估算出这样的结果 - 例如,一遍又一遍地随机传播皇后,并计算你在满足标准的位置上发生了多少次(没有一个人互相攻击); 例如,可能是0.0013%的次数.然后乘以(n*n)!/(n*(n-1))! - 所有可能配置的数量,并得到估计.但显然,这只是一个估计.你随意传播它们的时间越长,估计就越准确.