Count all solutions for the N Queens problem: How to get a result for N = 20 in an acceptable time?

Question

I was asked to write a program that counts the number of ways to place N queens on an NxN board without any queen attacking another. I have tried to think of every possible case to improve the performance, but my vb.net implementation takes almost 50 seconds 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

My teacher didn't give an exact time, but he asked to calculate the count for N=20 in an "acceptable time". I see that an increase of N by 1 multiplies the execution time by a factor of 7-8. That would mean this code would need days if not weeks to complete the task. Is this really possible in an acceptable time? How can this be achieved?

Answer 1

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.