图的应用2——骑士周游问题

问题描述

按照马走日的规则，要求从一个格子出发，走遍所有棋盘格恰好一次，称为周游

问题思路

按照图解决，通过将棋盘格作为顶点，按照马走日的规则，连边，建立每个棋盘
格的合法走棋步骤

使用方法

深度优先搜索 DFS

代码如下：

# 走棋位置函数
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 legalCoord(x, bdSize):
    if 0 <= x <= bdSize:
        return True
    else:
        return False


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], bdSize)
                ktGraph.addEdge(nodeId, nid)
    return ktGraph


def posToNodeId(row, col, bdSize):
    return row*bdSize+col


# DFS算法, n:层次；path：路径；u：当前顶点；limit：搜索总深度
def knightTour(n, path, u, limit):
    u.setColor('grey')
    # 当前顶点加入路径
    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 += 1
        # 无法探索到最深，该路径无用，返回上一顶点
        if not done:
            path.pop()
            u.setColor('white')
    else:
        done = True
    return done