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 *

This website stores some user agent data. These data are used to provide a more personalized experience and to track your whereabouts around our website in compliance with the European General Data Protection Regulation. If you decide to opt-out of any future tracking, a cookie will be set up in your browser to remember this choice for one year. I Agree, Deny
504