騎士周游問題
取一塊國(guó)際象棋棋盤和一顆騎士棋子（馬）。目標(biāo)是找到一系列走法坎缭，使得騎士對(duì)棋
盤上的每一格剛好都只訪問一次。這樣的一個(gè)移動(dòng)序列被稱為“周游路徑”
1.構(gòu)建騎士周游圖
from myGraph import Graph
def knightGraph(bdsize):
g = Graph()
for row in range(bdsize):
for col in range(bdsize):
nodeId = posToNodeId(row, col, bdsize)
newPositions = genLegalMoves(row, col, bdsize)
for i in newPositions:
newid = posToNodeId(i[0], i[1], bdsize)
g.addEdge(nodeId, newid)
return g
def genLegalMoves(row, col, bdsize):
newmoves = []
moveOffsets = [(-1, -2), (-1, 2), (-2, -1), (-2, 1), (1, -2), (1, 2), (2, -1), (2, 1)]
for i in moveOffsets:
newrow = row + i[0]
newcol = col + i[1]
if legalCoord(newrow, bdsize) and legalCoord(newcol, bdsize):
newmoves.append((newrow, newcol))
return newmoves
def legalCoord(x, bdsize):
if x >= 0 and x < bdsize:
return True
else:
return False
def posToNodeId(row, col, bdsize):
return row * bdsize + col
2.實(shí)現(xiàn)騎士周游
def knightTour(n, path, u, limit):
u.setColor('Gray')
path.append(u)
done = False
if n < limit:
nbrList = list(orderByAvail(u))
i = 0
while i < len(nbrList) and not done:
if nbrList[i].color == 'White':
done = knightTour(n+1, path, nbrList[i], limit)
i += 1
if not done:
path.pop()
u.setColor('White')
else:
done = True
return done
def orderByAvail(n):
resList = []
for v in n.getConnections():
if v.getColor() == 'White':
c = 0
for w in v.getConnections():
if w.getColor() == 'White':
c += 1
resList.append((c, v))
resList.sort(key=lambda x: x[0])
return [y[1] for y in resList]
if __name__ == '__main__':
g = knightGraph(8)
path = []
startVertex = g.getVertex(4)
knightTour(0, path, startVertex, 63)
for i in path:
print(i.getId(), end=' ')
輸出：
4 14 31 46 63 53 47 62 52 58 48 33 16 1 11 5 15 21 6 23 38 55 61 51 57 40 50 56 41 24 9 3 13 7 22 39 54 60 45 30 36 26 20 37 43 28 18 8 2 12 29 35 25 19 34 44 59 49 32 42 27 17 0 10
