I saw an online game around the knight’s tour problem the other day and it made me think of mathematics of chess puzzles. You know… Domination, independence (eight queens) etc. I thought it would be a good way to go back to writing some Python code after a long break.
The “Knight’s Tour” is a problem in which the objective is to move a knight, starting from any square on a chessboard to every other square landing on each square only once. Euler is said to be the first one to study this problem in 1759 on a 8 x 8 board. A knight’s tour is a Hamiltonian path. A closed tour is a Hamiltonian cycle i.e. the last square visited is also reachable from the first square by a single knight’s move. For all even n >= 6 there exists a closed knight’s tour on an n x n chessboard and an open knight’s tour if n >= 5.
We can create a matrix of size n x n with not visited cells filled with zeroes and every other cell to be filled with the order visited in the tour.
board = 
board_size = -1
def initiateBoard (board_dimensions):
board_size = board_dimensions
for i in range(0, board_size):
board.append(board_size*) #untouched board
Given knight’s behavior the possible moves relative to knight’s location are
knights_moves = ((-2,-1),(1,2),(2,-1),(-2,1),(2,1),(-1,2),(1,-2),(-1,-2))
But depending on where knight is on the board, not all moves will work so we should check whether a certain point is on the board and not visited.
def isAvailable(x, y):
if x < len(board) and y < len(board) and \
x >= 0 and y >= 0 and board[x][y]==0:
Naïve backtracking is a possible solution but for an 8×8 board, there exist 33,439,123,484,294 un-oriented paths so instead I will use Warnsdorff’’s rule to get to the solution a bit quicker. According to this heuristic method, knight always proceeds to the square from which it will have the fewest onward moves.
def getPossibleMoves(x, y):
possible_moves = 
for move in knights_moves:
cx,cy = x+move, y+move
def getNumMoves(x, y):
return len(getPossibleMoves(x, y))
def getNextMove (numMoves):
smallestIndex = 0
if not numMoves: #Nowhere to go
drawBoard() #Show the results
smallest = numMoves
for i in range(len(numMoves)):
if numMoves[i] < smallest:
smallest = numMoves[i]
smallestIndex = i
And finally the recursion to find the complete path
def solve (x,y,num_move):
board[x][y] == 0
board[x][y] = num_move
possible_moves = getPossibleMoves(x,y)
numOfMoves = 
nextMove = possible_moves[getNextMove(numOfMoves)]
def getKnightsPath (board_dimensions):
I’m leaving drawBoard() function to your imagination, but here is what I got using matplotlib.path.
For scaling to very large boards a divide-and-conquer solution would be necessary. If I can find some time, I’d also like to share a parallel implementation here.