На этом шаге мы рассмотрим пример такого решения.

    Во многих случаях представляет интерес найти только одно решение задачи, тем более что некоторые из них часто имеют единственное решение (например, задача судоку). Поэтому имеет смысл разработать методы перебора с возвратами, которые прекращают поиск решений, как только одно из них найдено. В языке Python есть возможность применить оператор return (возврат) сразу после обнаружения решения. Например, мы можем включать его сразу после вызова print_ chessboard(sol) в методе nqueens_all_sol() из примера 12.5. Однако во многих языках программирования этого делать нельзя.

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

def nqueens_one_sol(i, free_rows, free_pdiags,
                    free_sdiags, sol):
    n = len(sol)
    sol_found = False

    if i == n:
        return True
    else:
        k = 0
        while not sol_found and k < n:
            if (free_rows[k] and free_pdiags[i - k + n - 1]
                    and free_sdiags[i + k]):

                sol[i] = k

                free_rows[k] = False
                free_pdiags[i - k + n - 1] = False
                free_sdiags[i + k] = False

                sol_found = nqueens_one_sol(i + 1, free_rows,  
                                            free_pdiags,
                                            free_sdiags, sol)

                free_rows[k] = True
                free_pdiags[i - k + n - 1] = True
                free_sdiags[i + k] = True

            k = k + 1

        return sol_found


def nqueens_one_sol_wrapper(n):
    free_rows = [True] * n
    free_pdiags = [True] * (2 * n - 1)
    free_sdiags = [True] * (2 * n - 1)
    sol = [None] * n

    if nqueens_one_sol(0, free_rows, free_pdiags,
                       free_sdiags, sol):
        print_chessboard(sol)


def print_chessboard(sol):
    for i in range(0, len(sol)):
        print(sol[i], ' ', end='')
    print()

    Он очень похож на код для поиска всех решений. С одной стороны, метод-оболочка nqueens_one_sol_wrapper() вызывает в условном операторе if рекурсивную функцию перебора с возвратами и выдаёт решение, как только она смогла его найти. Отметим, что список sol меняется (его можно считать параметром, который передается по ссылке) и по завершении вызова метода будет содержать решение задачи, если оно существует. Другой вариант - выдать решение в начальном условии рекурсивной функции перед возвратом из неё. С другой стороны, функция nqueens_one_sol() сначала определяет логическую переменную sol_found с начальным значением False - признак того, что решение найдено. Цикл for заменён циклом while, чтобы завершить цикл, как только решение найдено. Тело цикла - то же, что в процедуре nqueens_all_sol(), только результат рекурсивного вызова присваивается переменной sol_found, значение которой возвращается по завершению цикла while.

    На следующем шаге мы рассмотрим задачу о сумме элементов подмножества.

Предыдущий шаг Содержание Следующий шаг