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):
global board
global board_size
global knights_moves
board_size = board_dimensions
for i in range(0, board_size):
board.append(board_size*[0]) #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[0]) and \
x >= 0 and y >= 0 and board[x][y]==0:
return True
else:
return False
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[0], y+move[1]
if isAvailable(cx,cy):
possible_moves.append((move[0],move[1]))
return possible_moves
def
getNumMoves(x, y):
return len(getPossibleMoves(x, y))
def
getNextMove (numMoves):
smallestIndex = 0
if not numMoves: #Nowhere to go
drawBoard() #Show the results
sys.exit(1)
smallest = numMoves[0]
for i in range(len(numMoves)):
if numMoves[i] < smallest:
smallest = numMoves[i]
smallestIndex = i
return smallestIndex
And finally the recursion to find the complete path
def
solve (x,y,num_move):
board[x][y] == 0assert
board[x][y] = num_move
possible_moves = getPossibleMoves(x,y)
numOfMoves = []
move for
possible_moves:in
numOfMoves.append(getNumMoves(x+move[0],y+move[1]))
nextMove = possible_moves[getNextMove(numOfMoves)]
solve(x+nextMove[0],y+nextMove[1],num_move+1)
def getKnightsPath (board_dimensions):
initiateBoard (board_dimensions)
solve(0,0,1)
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.
Nice. I’d have never thought of using path for this purpose. I see what you did there. Clever.