I have been working on the knight's tour simulation, and I have been stumped as to how to apply the Arnd Roth alteration to my python program. The snippet of the program here is the bulk of the calculations, and goes through the board, traveling to the the position that will have the least possible number of moves. What I want to change is if there are multiple positions that have the least number of moves(i.e. they both have 2 moves possible), I want to break the tie between them by measuring the distance between their position and the center and choosing the one farthest from it. How would I go about doing that?
dx = [-2, -1, 1, 2, -2, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]
# start the Knight from a random position
while tourTotal < tourMax:
chessBoardX = chessX; chessBoardY = chessY # width and height of the chessboard
chessBoard = [[0 for x in range(chessBoardX)] for y in range(chessBoardY)] # chessboard
# directions the Knight can move on the chessboard
currentX = random.randint(0, chessBoardX - 1)
currentY = random.randint(0, chessBoardY - 1)
currentFailures = 0
for k in range(chessBoardX * chessBoardY):
chessBoard[currentY][currentX] = k + 1
priorityQueue = [] # priority queue of available neighbors
for i in range(8):
newX = currentX + dx[i]; newY = currentY + dy[i]
if newX >= 0 and newX < chessBoardX and newY >= 0 and newY < chessBoardY:
if chessBoard[newY][newX] == 0:#if not visited
# count the available neighbors of the neighbor
counter = 0#counter is 0
for j in range(8):#max 8 moves
eX = newX + dx[j]; eY = newY + dy[j] #shows 1 move
if eX >= 0 and eX < chessBoardX and eY >= 0 and eY < chessBoardY:#if move is in parameters
if chessBoard[eY][eX] == 0: counter += 1 #if move is not visited, count is added
heappush(priorityQueue, (counter, i))#the amount of moves is pushed, along with the corresponding direction value
# move to the neighbor that has min number of available neighbors
if len(priorityQueue) > 0:
(p, m) = heappop(priorityQueue)
currentX += dx[m]; currentY += dy[m]
else: break
The (Manhattan) distance of a position (x,y) from the centre of an nx*ny rectangular board (0-based indices) is simply abs((nx-1)/2 - x) + abs((ny-1)/2 - y).
If you wanted Euclidean distance instead, it will be very similar.