Python骑士之旅-从前辈获取道路 [英] Knight's Tour in Python - Getting Path from Predecessors

问题描述

我正在尝试在Python中采用深度优先"搜索算法来解决骑士之旅"难题.我想我几乎成功了，为所有访问过的广场制作了前辈的字典.

I'm trying to adapt a Depth-First Search algorithm in Python to solve the Knight's Tour puzzle. I think I've nearly succeeded, by producing a dictionary of predecessors for all the visited squares.

但是，我被困在如何找到骑士的正常道路上.当前，使用 path()中 tour()的 current 返回值给出了 [(0，0)，((2，1)] .

However, I'm stuck on how to find the autual path for the Knight. Currently, using the current return value from tour() in path() gives a disappointing path of [(0, 0), (2, 1)].

我认为问题的症结在于确定在 tour()中的所有点都被访问过，然后返回当前的正方形，如果没有，则返回 None 无法解决.

I think the crux of the issue is determining at what point inside tour() all squares are visited and at that point returning the current square, and returning None if no solution is possible.

任何人都可以帮助我调整代码以产生正确的解决方案吗?

Can anyone please help me to adjust my code to produce a correct solution?

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))

推荐答案

您的方法存在以下问题:

Your approach has these issues:

• 该算法仅执行遍历(实际上不是搜索)，并且在访问(发现)所有节点后，堆栈将解开，直到从中弹出最后一个正方形.最后一个正方形是有史以来第一个被压入堆栈的正方形，因此肯定不是一个代表长路径末端的节点.
• 它不包含检测游览的逻辑.
• 基于发现的"数组，您将只分析一次广场，这意味着您希望找到一个没有回溯的游览，因为在第一次回溯之后，您将无法在某些地方再次使用已经访问过的广场变体路径.
• 前身数组是一种用于广度优先搜索的想法，但对于深度优先搜索并没有很好的用途
• 您认为有一个解决方案，但是您使用5x5网格调用该函数，并且在大小不一的木板上没有封闭的骑士之旅

尝试使用堆栈而不是递归来实现这一点，这会使您自己变得比需要困难.

Trying to implement this with a stack instead of recursion, is making things harder for yourself than needed.

我更改了您的代码以使用递归，并解决了上述问题.

I altered your code to use recursion, and deal with the above issues.

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 循环的状态放到堆栈上，即，您应该以某种方式知道循环何时结束.为此，您可以使堆栈成为其中的一个元素是仍然需要访问的邻居列表，包括当前"列表.因此，堆栈将是列表的列表:

To do this with an explicit stack, you need to also put the state of the for loop on the stack, i.e. you should somehow know when a loop ends. For this you could make the stack such that one element on it is a list of neighbors that still need to be visited, including the one that is "current". So the stack will be a list of lists:

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)))

我个人认为此代码比递归版本更令人困惑.您应该真正进行递归.

I personally find this code much more confusing than the recursive version. You should really go for recursion.

请注意，这种幼稚的方法远非高效.实际上，我们对6x6板感到幸运.如果您将偏移量以其他顺序列出，则很可能会花费更长的时间找到解决方案.

Note that this naive approach is far from efficient. In fact, we are a bit lucky with the 6x6 board. If you would have listed the offsets in a different order, chances are that it would take much longer to find the solution.

请查看Wikipedia的文章国王的游览，其中列出了一些算法，效率要高得多.

Please check Wikipedia's article Kinght's Tour, which lists a few algorithms that are far more efficient.

这篇关于Python骑士之旅-从前辈获取道路的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！