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:         

Leave a Reply

Your email address will not be published. Required fields are marked *

By continuing to use the site, you agree to the use of cookies. You can read more about it the Cookies&Privacy Policy Section Above. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this. You can read more about it the Cookies&Privacy Policy Section.

Close