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