"Put N Queens", can it possible to run within acceptable time with N = 20?

The task is count ho开发者_运维百科w many solutions to put N queens in NxN board. I have tried to thought every possible case to improve the performace, but it take almost 50s to run with N = 15. Here's what I've done:

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

Please tell me if it is possible (my teacher didn't give an exact time, he just tell "acceptable time". If it is possible, please tell me how, or just give me a clue!

I'd think of somehow taking into account that most solutions are nothing else but mirrored or rotated versions of other solutions. For example, you don't need to try and put the first queen in every column from left to right. It's probably enough if you only go from left to middle. This would already cut the time by half. If I am not mistaken, then for a 8x8 board, for example, putting the queen in 7th column is going to yield the same set of results as putting it in the 2nd column, only flipped. Why wouldn't it?

Adressing the exponential complexity problem: to be honest, 20 queens on a 20x20 board creates such a huge tree that I don't think there's any optimization capable of getting you an exact result in reasonable time. I just looked it up and there's almost 40 bilions solutions for n=20. See oeis.org/A000170 - n=20 has about 17 thousand times more solutions than n=15. I don't think we can optimize your algorithm by this factor. So even if we did our best and got down to as little as 2 seconds for n=15... it still means nearly 10 hours for n=20.

You can also think about it this way. If there's 39 029 188 884 solutions for 20x20 board with 20 queens, how much data is it? To remember each solution, you need to store 20 numbers from 1 to 20 (the horizontal position, or the x coordinate of each queen). You need 5 bits to represent a number < 20, hence 5*20 = 100 bits for each solution. 100 bits times 39 029 188 884 means 3634 gigabytes.

And that's the amount of data your program would have to generate (I know you don't need to save the solutions, you're just counting them: but you need to generate each of them so you can tick it off). Your teacher cannot reasonably expect you to write a program generating 3634 gigabytes of meaningful data in a heartbeat.

There are ways of estimating such a result - for example spreading the queens randomly over and over, and counting how many times you happen to get them in a position satisfying the criteria (none of them attack eachother); maybe 0.0013% of times, for example. Then multiply it by (n*n)! / (n*(n-1))! - the number of all possible configurations, and you get an estimation. But that's only an estimation, obviously. The longer you're spreading them haphazardly, the more accurate this estimation will be.

I've done combinatorial enumeration but not N queens specifically. Here's what I'd try (but again, as Morawski points out, lower your expectations).

1. Replace availableCols with an array listing the remaining columns. Store the diagonals as bit arrays. If there are too many to fit into one word, it's probably worth it to handle separately the diagonals containing only the first few rows (i.e., the ones that are relevant only near the top of the tree). Ideally testing a new queen would take only a couple of instructions. It helps if N is known to an aggressively optimizing compiler.

2. Use the available dihedral symmetry to enumerate only the lexicographically least solution in each orbit. Recover the overall count via the lemma that's not Burnside's. Symmetry breaking is expensive enough that there's an art to when to do it, but there's some low hanging fruit (e.g., don't place the queen in the first row in the upper columns). Placing by rows may not be the optimal strategy.

3. Test generalized arc consistency at interior nodes of the search tree. This is probably much too involved for homework, but I'm sure something like this is used in the really efficient computations behind the OEIS sequence.

The way this is usually done in programming contests is to put the results in an array in the code and just print the correct one. This is really fast but may not be what your teacher is looking for. Then again maybe it is.