骑士周游问题:修改算法，判断找到的周游路径最后能否回到起点，并找到回到起点的路径

Question

要求给出测试代码，谢谢！

from pythonds.graphs import Graph, Vertex

def knightGraph(bdSize):
    ktGraph = Graph()
    for row in range(bdSize):
        for col in range(bdSize):
            nodeId = posToNodeId(row, col, bdSize)
            newPositions = genLegalMoves(row, col, bdSize)
            for e in newPositions:
                nid = posToNodeId(e[0], e[1], 6)
                ktGraph.addEdge(nodeId, nid)
    return ktGraph


def legalCoord(x, bdSize):
    if x>=0 and x < bdSize: 
        return True
    else:
        return False

def posToNodeId(row,column,board_size):
    return (row * board_size) + column

def genLegalMoves(x, y, bdSize):
    newMoves = []
    moveOffsets = [(-1, -2), (-1, 2), (-2, -1), (-2, 1),
                (1, -2), (1, 2), (2, -1), (2, 1)]

    for i in moveOffsets:
        newX = x + i[0]
        newY = y + i[1]
        if legalCoord(newX, bdSize) and legalCoord(newY, bdSize):
            newMoves.append((newX, newY))
    return newMoves


def knightTour(n, path, u, limit):
    u.setColor('gray')
    path.append(u)
    if n < limit:
        nbrList = list(u.getConnections()) 
        i=0
        done = False
        while i < len(nbrList) and not done:
            if nbrList[i].getColor() == 'white':
                done = knightTour(n+1,path,nbrList[i],limit)
            i=i+1
        if not done: # 准备回溯
            path.pop()
            u.setColor('white')
    else:
        done = True


    return done



if __name__ == '__main__':
    # suppose board size is 6
    G = knightGraph(6)
    # you can choose any nodeid as the starting point
    u = G.getVertex(1)
    limit = 6 * 6
    # initial path is an empty list
    path = list()
    # we already have an initial node, therefore n equals 1
    n = 1
    # print whether successfully find a path that can traverse all of the nodes
    k = knightTour(n, path, u, limit)
    print("骑士周游的路径为：")
    for node in path:
       print(node.getId(), end=' ')

#text code
#骑士周游的路径为：
#1 9 5 16 8 0 13 2 6 14 10 21 29 33 25 12 20 24 32 28 17 4 15 19 30 26 34 23 27 31 

Answer 1

你题目的解答代码如下：

from pythonds.graphs import Graph, Vertex

def knightGraph(bdSize):
    ktGraph = Graph()
    for row in range(bdSize):
        for col in range(bdSize):
            nodeId = posToNodeId(row, col, bdSize)
            newPositions = genLegalMoves(row, col, bdSize)
            for e in newPositions:
                nid = posToNodeId(e[0], e[1], 6)
                ktGraph.addEdge(nodeId, nid)
    return ktGraph


def legalCoord(x, bdSize):
    if x>=0 and x < bdSize:
        return True
    else:
        return False

def posToNodeId(row,column,board_size):
    return (row * board_size) + column

def genLegalMoves(x, y, bdSize):
    newMoves = []
    moveOffsets = [(-1, -2), (-1, 2), (-2, -1), (-2, 1),
                (1, -2), (1, 2), (2, -1), (2, 1)]

    for i in moveOffsets:
        newX = x + i[0]
        newY = y + i[1]
        if legalCoord(newX, bdSize) and legalCoord(newY, bdSize):
            newMoves.append((newX, newY))
    return newMoves


def knightTour(n, path, u, limit):
    u.setColor('gray')
    path.append(u)
    if n < limit+1:
        nbrList = list(u.getConnections())
        i=0
        done = False
        while i < len(nbrList) and not done:
            if n < limit and nbrList[i].getColor() == 'white' or n == limit and nbrList[i]==path[0]:
                done = knightTour(n+1,path,nbrList[i],limit)
            i=i+1
        if not done: # 准备回溯
            path.pop()
            u.setColor('white')
    else:
        done = True


    return done



if __name__ == '__main__':
    # suppose board size is 6
    G = knightGraph(6)
    # you can choose any nodeid as the starting point
    u = G.getVertex(1)
    limit = 6 * 6
    # initial path is an empty list
    path = list()
    # we already have an initial node, therefore n equals 1
    n = 1
    # print whether successfully find a path that can traverse all of the nodes
    k = knightTour(n, path, u, limit)
    print("骑士周游的路径为：")
    for node in path:
       print(node.getId(), end=' ')

如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!