Решение проблемы с алгоритмом решения / генерации судоку

Я создаю программу, которая будет генерировать головоломки судоку на vb.net, и из-за того, как я это делаю, мне нужно, чтобы она решала позицию доски (доступ к ячейкам в определенном случайном порядке), а затем снова решала ее в обратный порядок. Для этого я использую рекурсивный решатель.

Это код, с которым я работаю:

Public Function solve(ByRef board() As Integer) As Boolean
    For i = 0 To 80
        If board(order(i)) = 0 Then
            For j = 1 To 9
                board(order(i)) = j
                If check_conflicts(board, order(i)) = False Then
                    If solve(board) = True Then
                        Return True
                    End If

                End If
            Next
            board(order(i)) = 0
            Return False
        End If
    Next

    Return True
End Function

где check_conflicts - это функция, которая определяет, конфликтует ли конкретное назначение ячейки напрямую с платой (следовательно, доска передается и индекс ячейки order(i) также передается). Эта функция работает должным образом, когда order - это список от 0 до 80, однако, если order - это случайно перемешанный список, тогда функция занимает невероятно много времени (иногда более минуты), но обычно получает правильный ответ. Когда порядок представляет собой список чисел от 80 до 0, функция ничего не решает и всегда возвращает false.

Я пробовал пройти через код, но с рекурсивной функцией это сложно. Интересно, может ли кто-нибудь увидеть мою логическую ошибку, спасибо!


vb.net algorithm sudoku
person maxG795    schedule 23.02.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Эта функция работает, как ожидалось, когда порядок представляет собой список от 0 до 80, однако, если порядок представляет собой случайно перемешанный список, тогда функция занимает невероятно много времени (иногда более минуты), но обычно получает правильный ответ.

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

Когда порядок представляет собой список чисел от 80 до 0, функция ничего не решает и всегда возвращает false.

Пара предложений:

1) Попробуйте заменить order(i) на 80-i, чтобы убедиться, что проблема не в функции order();

2) Каждый раз, когда вы вызываете check_conflicts(board, order(i)), вызывайте также check_conflicts(inverse(board), 80-order(i)) и генерируйте исключение, если их результаты не равны.

person Anton    schedule 23.02.2014
comment
спасибо за ответ, я попробовал ваши предложения и понял, что причина, по которой он не работал в обратном направлении, была из-за ошибки в наборах ограничений, которые сделали головоломку невозможной. Я подозревал то же самое в алгоритме, который по своей сути медленный, думаю, мне нужно реализовать некоторые оптимизации - person maxG795; 24.02.2014