Python program showing Knight’s Tour iterative algorithm using ASCII chars for demonstration.

# ? 2017 TheFlyingKeyboard and released under MIT License
# theflyingkeyboard.net
import os

knightMoves = [ [ 2, 1 ], [ 1, 2 ], [ -1, 2 ], [ -2, 1 ], [ -2, -1 ], [ -1, -2 ], [ 1, -2 ], [ 2, -1 ] ];

def generateBoard(size):
line = []
board = []

for i in range(0, size):
line.append(' ')

for i in range(0, size):
board.append(list(line))

return board

def checkIfCanMove(nextKnightXPos, nextKnightYPos, moveNum, board):
xMove = nextKnightXPos + knightMoves[moveNum][1]
yMove = nextKnightYPos + knightMoves[moveNum][0]

if (xMove >= 0 and xMove < len(board)) and (yMove >= 0 and yMove < len(board)) and board[yMove][xMove] != 'X' and board[yMove][xMove] != '@':
return True
else:
return False

def calculatePossibleMoves(nextKnightXPos, nextKnightYPos, board):
moves = 0

for i in range(0, 8):
if checkIfCanMove(nextKnightXPos, nextKnightYPos, i, board):
moves += 1

return moves

def printBoard(board):
for s in board:
print(*s)

return

def solveBoard(knightXPos, knightYPos, board):
moves = []
smallestNumber = 0
smallestNumberIndex = 0
xMove = 0
yMove = 0

for i in range(0, len(board) * len(board)):
printBoard(board)
print("Turn number:", i)
print("Press any key to continue...")

moves[:] = []

for j in range(0, 8):
xMove = knightXPos + knightMoves[j][1]
yMove = knightYPos + knightMoves[j][0]

if checkIfCanMove(knightXPos, knightYPos, j, board):
moves.append(calculatePossibleMoves(xMove, yMove, board))
else:
moves.append(-1)

smallestNumber = 8
smallestNumberIndex = 0

for j in range(0, 8):
if moves[j] < smallestNumber and moves[j] >= 0:
smallestNumber = moves[j]
smallestNumberIndex = j

board[knightYPos][knightXPos] = 'X'

knightXPos += knightMoves[smallestNumberIndex][1]
knightYPos += knightMoves[smallestNumberIndex][0]

board[knightYPos][knightXPos] = '@'

input();

os.system('cls' if os.name == 'nt' else 'clear')

return

gameBoard = []
size = int(input("Enter size of a board"))
xPosition = 0
yPosition = 0

if size > 4:
gameBoard = generateBoard(size)

xPosition = int(input("Enter Knight's X position"))
yPosition = int(input("Enter Knight's Y position"))

gameBoard[yPosition][xPosition] = '&'

solveBoard(xPosition, yPosition, gameBoard)
else:
print("Size of board must be > 4")

Python Knight’s Tour Iteration Algorithm
Tagged on: