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)