«Положите 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-м столбце, только перевернутый. Почему бы и нет?

Решение проблемы экспоненциальной сложности: Если честно, 20 ферзей на доске 20х20 создают такое огромное дерево, что я не думаю, что есть какая-либо оптимизация, способная дать вам точный результат в разумные сроки. Я только что посмотрел, и есть почти 40 миллиардов решений для n = 20. См. oeis.org / A000170 - n = 20 имеет примерно в 17 тысяч раз больше решений, чем n = 15. Я не думаю, что мы можем оптимизировать ваш алгоритм по этому фактору. Таким образом, даже если мы приложили все усилия и получили всего 2 секунды для n = 15 ... это все равно означает почти 10 часов для n = 20.

Вы также можете думать об этом таким образом. Если существует 39 029 188 884 решений для платы 20х20 с 20 ферзями, то сколько это будет? Чтобы запомнить каждое решение, вам нужно сохранить 20 чисел от 1 до 20 (горизонтальная позиция или координата x каждой ферзя). Вам нужно 5 бит, чтобы представить число <20, следовательно, 5 * 20 = 100 бит для каждого решения. 100 бит раз 39 029 188 884 означает 3634 гигабайта. </p>

И это тот объем данных, который должна сгенерировать ваша программа (я знаю, что вам не нужно сохранять решения, вы просто их подсчитываете, но вам нужно сгенерировать каждое из них, чтобы вы могли поставить галочку) , Ваш учитель не может разумно ожидать, что вы напишете программу, генерирующую 3634 гигабайта значимых данных в одно мгновение.

Существуют способы оценки такого результата - например, случайное распределение ферзей случайным образом и подсчет того, сколько раз вам выпало получить их в положении, удовлетворяющем критериям (никто из них не атакует друг друга); например, 0,0013% раз. Затем умножьте это на (n * n)! / (n * (n-1))! - количество всех возможных конфигураций, и вы получите оценку. Но это только оценка, очевидно. Чем дольше вы их беспорядочно распространяете, тем точнее будет эта оценка.

Answer 2

Я сделал комбинаторное перечисление, но не определил N королев. Вот что я попробую (но опять же, как указывает Моравский, снизьте свои ожидания).

1. Заменить availableCols на массив, в котором перечислены оставшиеся столбцы. Храните диагонали как битовые массивы. Если их слишком много, чтобы уместиться в одно слово, возможно, стоит по отдельности обработать диагонали, содержащие только первые несколько строк (то есть те, которые имеют отношение только к вершине дерева). В идеале тестирование новой королевы потребовало бы только пары инструкций. Это помогает, если N известен агрессивно оптимизирующему компилятору.

2. Используйте имеющуюся двугранную симметрию , чтобы перечислить только наименее лексикографически решение на каждой орбите. Восстановите общий счет с помощью леммы , которая не Бернсайда. Нарушение симметрии достаточно дорого, так что есть искусство, когда это делать, но есть какой-то низко висящий фрукт (например, не помещайте королеву в первый ряд в верхних столбцах). Размещение по строкам не может быть оптимальной стратегией.

3. Тест обобщенная согласованность дуг во внутренних узлах дерева поиска. Вероятно, это слишком сложно для домашней работы, но я уверен, что нечто подобное используется в действительно эффективных вычислениях за последовательностью OEIS.

Answer 3

Способ, которым это обычно делается в соревнованиях по программированию, состоит в том, чтобы поместить результаты в массив в коде и просто напечатать правильный. Это действительно быстро, но, возможно, не то, что ищет ваш учитель. С другой стороны, может быть, это так.