Поиск перебором решения задачи о 7-ми кенигсбергских мостах

konigsberg_bridges.py

'''
Программа для нахождения перебором решения задачи о 7-ми кенигсбергских мостах.
см. https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%81%D0%B5%D0%BC%D0%B8_%D0%BA%D1%91%D0%BD%D0%B8%D0%B3%D1%81%D0%B1%D0%B5%D1%80%D0%B3%D1%81%D0%BA%D0%B8%D1%85_%D0%BC%D0%BE%D1%81%D1%82%D0%B0%D1%85
Решения этой задачи не существует, что доказал Леонард Эйлер.
'''


bridges = (
    (1, 2),
    (1, 2),
    (2, 3),
    (1, 3),
    (3, 4),
    (1, 4),
    (1, 4)
)


def bridges_of_isle(isle):
    '''Возвращает список мостов, которые заходят на остров под номером isle'''
    return (b for b in bridges if isle in b)


def walk_isle(isle, path, visited):
    '''Рекурсивная функция для "обхода" одного острова,
    где isle - номер острова,
    path - последовательность посещённых островов, 
    visited - последовательность посещённых мостов'''
    if visited == bridges:
        print("Есть решение: ", "-".join(str(i) for i in path))
    elif all(b in visited for b in bridges_of_isle(isle)):
        print("Тупик:", "-".join(str(i) for i in path))
    else:
        for b in bridges_of_isle(isle):
            if b not in visited:
                walk_isle(b[0] if b[0] != isle else b[1],
                          path + (isle,), visited + (b,))


for isle in range(1, 5):
    walk_isle(isle, (isle, ), ())