7777733333
2022-05-24 19:28
采纳率: 85.7%
浏览 48

骑士周游问题根据已有代码,编写测试代码打印出周游路径后,再修改算法判断找到的周游路径是否能回到起点


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

2条回答 默认 最新

相关推荐 更多相似问题