Writing
Finding A Knight's Tour
An exploration of the Knight's Tour problem using backtracking and Warnsdorff's heuristic in Python.
A Knight’s Tour is a sequence of moves done by a knight on a chessboard such that it visits each and every square exactly once. Subsequently, the objective of the Knight’s Tour problem is to determine whether there exists a Knight’s Tour from a given starting position. In graph theory terms, it is a form of Hamiltonian path where you visit each vertex of the graph exactly once along the path. Tours can also be cyclic or closed if the final square is a knight’s move away from the first and acyclic or open otherwise.
On a typical 8 x 8 chessboard, according to this paper, the number of undirected closed knight’s tours was computed to be 13,267,364,410,532, (directed would be twice that). The number of directed open tours on a 8 x 8 was not actually known and estimated to be about 2x10^16 until in 2013, Alex Chernov computed that the number is 19,591,828,170,979,904.
On an irregular board, the smallest rectangular board dimensions in which there is an open knight’s tour is 3 x 4.
I was trying to solve problem out manually on a chessboard. There are some strategies if you start from a corner, but I keep running into dead-ends, if I start from a non-corner position. So, I resort to programming and here are some of my attempts to search for a knight’s tour.
Backtracking
With a depth-first traversal with backtracking, a knight tour can be searched. The gist is that at each branch of traversal, go with the first branch and if the search reaches a dead-end, go back a step and try other alternatives. Eventually, either a tour will be found or there is no possible knight tour from the given starting position.
X = 0
Y = 1
def chess2index(p, boardsize):
x = boardsize[X] - int(p[1])
y = ord(p[0]) - ord('a')
return x, y
def is_legal(pos, board, boardsize):
return 0 <= (pos[X]) < boardsize[X] and \
0 <= (pos[Y]) < boardsize[Y] and \
not board[pos]
def board_string(board, boardsize):
string = ''
for x in range(boardsize[X]):
for y in range(boardsize[Y]):
string += '%3d' % board[(x, y)]
string += '\n'
return string
def knight_tour(currentpos, board, count):
if count >= boardsize[X] * boardsize[Y]:
return True
for d in offsets:
newpos = currentpos[X]+d[X], currentpos[Y]+d[Y]
if is_legal(newpos, board, boardsize):
count += 1
board[newpos] = count
if knight_tour(newpos, board, count):
return True
else:
board[newpos] = 0
count -= 1
return False
if __name__ == '__main__':
n = int(raw_input('n: '))
boardsize = (n, n)
start = chess2index(raw_input('Start: '), boardsize)
offsets = ((1, 2), (-1, 2), (1, -2), (-1, -2),
(2, 1), (-2, 1), (2, -1), (-2, -1))
board = {(x, y):0 for x in range(boardsize[X]) for y in range(boardsize[Y])}
count = 1
board[start] = count
if knight_tour(start, board, count):
print board_string(board, boardsize)
else:
print "No knight's tour"
Most of the magic happens in the knight-tour function in which, the search starts from the initial position on the board (count=1). From the current position, possible legal knight moves are generated and tried out by incrementing the count and marking it on the board. If a move turns out to be leading a dead end, reset the board position and the count will be decremented and it would reach the end of the function (return False) and exit from a recursion instance. Eventually, a knight’s tour will be found (count == total) provided that there is one.
This approach works reasonably well for small boards but as the size of the board grows (N >= 7 onwards ), the search will take exponentially longer as there would be more “center” pieces which have 8 possible moves.
Warnsdorff’s rule
In order to improve from that, Warnsdorff’s rule can be applied. Warnsdorff’s rule is a heuristic which states that in each step of the tour, the square with the least possible moves the knight can make from that square is favored. If a tie occurs, it may be broken arbitrarily.
def next_possible_moves(current, board, boardsize):
next_moves = [(current[X]+d[X], current[Y]+d[Y]) for d in offsets]
next_moves = [p for p in next_moves if is_legal(p, board, boardsize)]
return next_moves
def warnsdorff(current, board, boardsize):
moves = []
for move in next_possible_moves(current, board, boardsize):
moves.append((move, len(next_possible_moves(move, board, boardsize))))
return sorted(moves, key=lambda x:x[1])
def knight_tour(start, board, count):
current = start
while count < len(board):
newpos = warnsdorff(current, board, boardsize)
if newpos:
count += 1
board[newpos[0][0]] = count
current = newpos[0][0]
else:
return False
return True
The idea is to have a list of possible moves (next_possible_moves()) and calculate and store the number of possible moves from each of those moves (warnsdorff()) and choose the move with fewest onward moves. Reaching a dead-end means, there are no possible moves returning from the warnsdorff function.
X = 0
Y = 1
def chess2index(p, boardsize):
x = boardsize[X] - int(p[1])
y = ord(p[0]) - ord('a')
return x, y
def is_legal(pos, board, boardsize):
return 0 <= (pos[X]) < boardsize[X] and \
0 <= (pos[Y]) < boardsize[Y] and \
not board[pos]
def board_string(board, boardsize):
string = ''
for x in range(boardsize[X]):
for y in range(boardsize[Y]):
string += '%3d' % board[(x, y)]
string += '\n'
return string
def next_possible_moves(current, board, boardsize):
next_moves = [(current[X]+d[X], current[Y]+d[Y]) for d in offsets]
next_moves = [p for p in next_moves if is_legal(p, board, boardsize)]
return next_moves
def warnsdorff(current, board, boardsize):
moves = []
for move in next_possible_moves(current, board, boardsize):
moves.append((move, len(next_possible_moves(move, board, boardsize))))
return sorted(moves, key=lambda x:x[1])
def knight_tour(start, board, count):
current = start
while count < len(board):
newpos = warnsdorff(current, board, boardsize)
if newpos:
count += 1
board[newpos[0][0]] = count
current = newpos[0][0]
else:
return False
return True
if __name__ == '__main__':
n = int(raw_input('N: '))
boardsize = (n, n)
start = chess2index(raw_input('Start: '), boardsize)
offsets = ((1, 2), (-1, 2), (1, -2), (-1, -2),
(2, 1), (-2, 1), (2, -1), (-2, -1))
board = {(x, y):0 for x in range(boardsize[X]) for y in range(boardsize[Y])}
count = 1
board[start] = count
if knight_tour(start, board, count):
print board_string(board, boardsize)
else:
print "No knight's tour"
Output
> python knights-tour.py
N: 8
Start: a5
44 17 20 3 26 41 22 5
19 2 43 46 21 4 25 40
16 45 18 27 42 51 6 23
1 28 57 54 47 24 39 52
56 15 48 35 58 53 50 7
29 12 55 64 49 34 59 38
14 63 10 31 36 61 8 33
11 30 13 62 9 32 37 60
> python knights-tour.py
N: 10
Start: e2
11 92 13 86 9 80 41 82 7 76
14 85 10 79 42 83 8 77 40 71
91 12 93 84 87 78 81 72 75 6
96 15 90 43 94 73 88 65 70 39
57 44 95 100 89 64 69 74 5 62
16 97 58 55 68 99 66 63 38 25
45 56 33 98 59 54 37 24 61 4
32 17 46 49 36 67 60 53 26 23
47 34 19 30 1 50 21 28 3 52
18 31 48 35 20 29 2 51 22 27
This approach works well for really big boards as well. A Knight’s Tour can be found in a few seconds during my testing with big boards. (N=200,300,400)
As you can see, I rely on Python’s sorted() function and didn’t do anything special for ties. However, as far as I have researched, there are some approaches to break the ties in more specific manners instead of choosing arbitrarily.