Knight's Tour в Python - путь от предшественников

Question

Я пытаюсь адаптировать алгоритм поиска в глубину в Python, чтобы решить загадку Knight's Tour. Я думаю, что я почти добился успеха, создав словарь предшественников для всех посещенных квадратов.

Однако я застрял в том, как найти автоматический путь для Рыцаря. В настоящее время использование current возвращаемого значения из tour() в path() дает неутешительный путь [(0, 0), (2, 1)].

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

Может кто-нибудь помочь мне настроить мой код для получения правильного решения?

offsets = (
    (-1, -2), (1, -2),
    (-2, -1), (2, -1),
    (-2, 1), (2, 1),
    (-1, 2), (1, 2),
)

def is_legal_pos(board, pos):
    i, j = pos
    rows = len(board)
    cols = len(board[0])
    return 0 <= i < rows and 0 <= j < cols


def path(predecessors, start, goal):
    current = goal
    path = []
    while current != start:
        path.append(current)
        current = predecessors[current]
    path.append(start)
    path.reverse()
    return path


def tour(board, start):
    stack = []
    stack.append(start)
    discovered = set()
    discovered.add(start)
    predecessors = dict()
    predecessors[start] = None

    while stack:
        current = stack.pop()
        for move in offsets:
            row_offset, col_offset = move
            next = (current[0] + row_offset, current[1] + col_offset)
            if is_legal_pos(board, next) and next not in discovered:
                stack.append(next)
                discovered.add(next)
                predecessors[next] = current

    return predecessors, current


board = [[" "] * 5 for row in range(5)]
start = (0, 0)
predecessors, last = tour(board, start)
print(predecessors)
print(path(predecessors, start, last))

Answer 1

Ваш подход имеет следующие проблемы:

• Алгоритм просто выполняет обход (а не поиск), и когда все узлы были посещены (обнаружены), стек будет развернут, пока не будет извлечен последний квадрат от него. Этот последний квадрат является первым, когда-либо помещенным в стек, поэтому, конечно, он не является узлом, представляющим конец длинного пути.
• В него не входит лог c для обнаружения обхода.
• На основе «обнаруженного» массива вы будете анализировать квадрат только один раз, что означает, что вы ожидаете найти тур без возврата, так как после первого возврата вы не сможете повторно использовать уже посещенные квадраты в некотором варианте пути.
• Массив предшественника - это идея, которая используется при поиске в ширину, но не очень подходит для поиска в глубину
• Вы предполагаете, что есть решение , но вы вызываете функцию с сеткой 5x5, и на закрытых досках не проводится закрытый тур коня

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

Я изменил ваш код для использования рекурсии и решил вышеуказанные проблемы.

offsets = (
    (-1, -2), (1, -2),
    (-2, -1), (2, -1),
    (-2, 1), (2, 1),
    (-1, 2), (1, 2),
)


# We don't need the board variable. Just the number of rows/cols are needed:
def is_legal_pos(rows, cols, pos):
    i, j = pos
    return 0 <= i < rows and 0 <= j < cols


def tour(rows, cols, start):
    discovered = set()
    n = rows * cols

    def dfs(current):  # Use recursion
        discovered.add(current)
        for move in offsets:
            row_offset, col_offset = move
            # Don't name your variable next, as that is the name of a native function
            neighbor = (current[0] + row_offset, current[1] + col_offset)
            # Detect whether a closed tour was found
            if neighbor == start and len(discovered) == n:
                return [start, current]  # If so, create an extendable path
            if is_legal_pos(rows, cols, neighbor) and neighbor not in discovered:
                path = dfs(neighbor)
                if path:  # Extend the reverse path while backtracking
                    path.append(current)
                    return path
        # The choice of "current" did not yield a solution. Make it available
        # for a later choice, and return without a value (None)
        discovered.discard(current)

    return dfs(start)

# No need for a board variable. Just number of rows/cols is enough.
# As 5x5 has no solution, call the function for a 6x6 board:
print(tour(6, 6, (0, 0)))

Чтобы сделать это с явным стеком, вам также нужно поместить состояние for l oop в стек, т.е. вы должны как-то знать, когда заканчивается al oop. Для этого вы можете сделать стек таким, чтобы один элемент в нем представлял собой список соседей, которые еще необходимо посетить, включая того, который является «текущим». Таким образом, в стеке будет список списков:

offsets = (
    (-1, -2), (1, -2),
    (-2, -1), (2, -1),
    (-2, 1), (2, 1),
    (-1, 2), (1, 2),
)


# We don't need the board variable. Just the number of rows/cols are needed:
def is_legal_pos(rows, cols, pos):
    i, j = pos
    return 0 <= i < rows and 0 <= j < cols


def tour(rows, cols, start):
    discovered = set()
    n = rows * cols
    stack = [[start]]

    while stack:
        neighbors = stack[-1]
        if not neighbors:  # Need to backtrack...
            stack.pop()
            # remove the node that ended this path, and unmark it
            neighbors = stack[-1]
            current = neighbors.pop(0)
            discovered.discard(current)
            continue
        while neighbors:
            current = neighbors[0]
            discovered.add(current)
            neighbors = []   # Collect the valid neighbors
            for move in offsets:
                row_offset, col_offset = move
                # Don't name your variable next, as that is the name of a native function
                neighbor = (current[0] + row_offset, current[1] + col_offset)
                # Detect whether a closed tour was found
                if neighbor == start and len(discovered) == n:
                    path = [start]  # If so, create the path from the stack
                    while stack:
                        path.append(stack.pop()[0])
                    return path
                if is_legal_pos(rows, cols, neighbor) and neighbor not in discovered:
                    neighbors.append(neighbor)
            # Push the collection of neighbors: deepening the search
            stack.append(neighbors)


# No need for a board variable. Just number of rows/cols is enough.
# As 5x5 has no solution, call the function for a 6x6 board:
print(tour(6, 6, (0, 0)))

Лично я нахожу этот код намного более запутанным, чем рекурсивная версия. Вы действительно должны go для рекурсии.

Обратите внимание, что этот наивный подход далеко не эффективен. На самом деле нам немного повезло с доской 6х6. Если бы вы перечислили смещения в другом порядке, есть вероятность, что для поиска решения потребуется гораздо больше времени.

Пожалуйста, ознакомьтесь со статьей Википедии Kinght's Tour , в которой перечислены несколько алгоритмов, которые гораздо эффективнее.