# A chess knight's moves

A chess knight's horse has hurt its leg, and because of that it has to step on every field on its path in order to move in the shape of the letter L. Also try to imagine a chess board: for example when the knight tries to jump from the square a1 to the square b3, our injured knight has to step on fields a2 and a3 or on fields b1 and b2. Will that knight be able to step on all fields on a board of dimensions 5x11 in such a way that it will step on every field of that board?

• Where does it start? And, do you mean "every field once"? Is it possible to move $a1 \to a2 \to b2 \to b3$? Oct 16, 2016 at 14:49
• @AdLibitum Usually, the shape is described with the help of the squares, a knight moves. And this shape is an "L". Even if you insist on a $2x3$-shape, it can be viewed as an "L". But I agree that the name "horse" is very unusual in chess. Oct 16, 2016 at 15:18
• @Peter: In European languages. The name of the piece in many of the precursors translates as horse, and its name in some non-European modern languages also translates as horse. Oct 17, 2016 at 11:53
• It can start anywhere you want. It only has to step on every square constituting its "L" shape of movement. Will it be able to touch (walk over) every field(square) on the chess board in such a way? Oct 23, 2016 at 15:06
• @Peter In some (at least three) Slavic languages a knight piece is called “horse” and its name ‘knight’ sounds strange to native speakers. A piece name “bishop” sounds even more strange for us, because we call this piece “elephant”. :-) Oct 25, 2016 at 7:25

## 2 Answers

So, the language and Soviet math contest kind of this problem suggested me to search it in Russian Internet. I traced its origins back to XXXIII Ural tournament of young mathematicians, where it was presented at 2009, February 27 at so-called math fight and was attributed to A. Adel’shin (А. Адельшин). Problems for smaller boards can be found here (both pages are of course in Russian). A positive solution was found in Russian math magazine “Kvantik” (a small quantum) from 2014, August:

• Did the original Russian problem impose another condition, not mentioned by our OP here, that the knight may not step on a square more than once?
– bof
Oct 25, 2016 at 9:39
• @bof Yes, of course. Oct 25, 2016 at 9:41

Not satisfied with a single solution, I ran a python script to enumerate all possible solutions. It produced the following 9 tours (28 tours before discarding symmetric ones).

# +-#-+-+ +-# +-#-+-+
| |     | | | |     |
+ + +-+-# + + + +-+-#
| | |     | | | |
+-# # #-+ # +-# # #-+
| | | |     | | |
#-+-+ + + + #-+-+ + +
|     | | | |     | |
+-+-#-+ #-+ +-+-#-+ #

# +-#-+-+ +-#-+-+ #-+
| |     | |     | | |
+ + +-+-# + +-+-# + +
| | |     | |     | |
+-# # #-+ # # +-#-+ #
| | | | | |     |
#-+-+ + + + + + #-+-+
|     | | | | | |
+-+-#-+ #-+ +-# +-+-#

# +-#-+-+ +-+-#-+ #-+
| |     | |     | | |
+ + +-+-# #-+-+ + + +
| | |         | | | |
+-# # #-+ #-+ # #-+ #
| | | | | |     |
#-+-+ + + + + + #-+-+
|     | | | | | |
+-+-#-+ #-+ #-+ +-+-#

#-+-+ #-+ +-#-+-+ #-+
| | | |     | | |
+-+-# + + + +-+-# + +
|     | | | |     | |
# +-#-+ # # # +-#-+ #
| |     | | | |     |
+ + #-+-+ + + + #-+-+
| | |     | | | |
+-# +-+-#-+ +-# +-+-#

#-+-+ #-+ +-+-#-+ #-+
| | | |     | | |
+-+-# + + #-+-+ + + +
|     | |     | | | |
# +-#-+ # #-+ # #-+ #
| |     | | | |     |
+ + #-+-+ + + + #-+-+
| | |     | | | |
+-# +-+-#-+ #-+ +-+-#

#-+-+ +-# +-+-#-+ #-+
| | | |     | | |
+-+-# + + #-+-+ + + +
|     | |     | | | |
# +-# # +-#-+ # #-+ #
| | | |     | |     |
+ + + +-+-# + + #-+-+
| | |     | | | |
+-# +-#-+-+ #-+ +-+-#

#-+-+ +-#-+-+ +-#-+-+
| |     | |     |
+-+-# + +-+-# + +-+-#
|     | |     | |
# +-# # #-+-+ # #-+-+
| | | |     | |     |
+ + + +-+-# # +-+-# #
| | |     | |       |
+-# +-#-+-+ +-+-#-+-+

#-+-+ +-#-+-+ +-+-#-+
| |     | |     |
+-+-# + +-+-# # +-# +
|     | |     | | | |
# +-# # #-+-+ + + + #
| | | |     | | | |
+ + + +-+-# # +-# +-#
| | |     | |       |
+-# +-#-+-+ +-+-#-+-+

#-+-+ +-+-#-+ #-+ #-+
| |     | | | | |
+-+-# #-+-+ + + + + +
|         | | | | | |
# +-# +-# # #-+ #-+ #
| | | | | |         |
+ + + + + +-+-# #-+-+
| | | | |     | |
+-# +-# +-#-+-+ +-+-#


Here's the python script. Mostly brute-force, pruning out situations where the unvisited squares are not connected or have 2 vertices with only one adjacent unvisited square (since the knight must end his tour at such a square). Runs in under a minute.

BOARD_WIDTH = 11
BOARD_HEIGHT = 5

on_board = lambda (x,y): 0 <= x < BOARD_WIDTH and 0 <= y < BOARD_HEIGHT

adjacent = lambda (x,y): [p for p in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)] if on_board(p)]

VERTICES = set((x,y) for x in range(BOARD_WIDTH) for y in range(BOARD_HEIGHT))

def is_admissible(cur, visited):
# count "alcoves", places the knight must end his tour
# if there are more than one, a tour doesn't exist.
alcove_count = 0
for v in VERTICES:
if v in visited: continue

# squares next to the knight don't count as alcoves
if abs(cur[0]-v[0]) + abs(cur[1]-v[1]) == 1: continue

deg = len(filter(lambda p:not p in visited, adjacent(v)))
if deg == 1:
alcove_count += 1
if alcove_count > 1:
# print 'too many alcoves.'
return False

unvisited = VERTICES - visited
for u in unvisited:
break

found = [u]
unvisited.remove(u)

while found:
u = found.pop()
for v in adjacent(u):
if v in unvisited and not v in visited and not v in found:
found.append(v)
unvisited.remove(v)
if unvisited:
# print 'not connected.'
return False

return True

def search(path):
global longest_so_far

if len(path) == len(VERTICES):
yield path
return

cur = path[-1]
visited = set(path)

if not is_admissible(cur, visited):
return

for L in [
[(1,0),(2,0),(2,1)],
[(1,0),(2,0),(2,-1)],
[(1,0),(1,1),(1,2)],
[(1,0),(1,-1),(1,-2)],

[(-1,0),(-2,0),(-2,1)],
[(-1,0),(-2,0),(-2,-1)],
[(-1,0),(-1,1),(-1,2)],
[(-1,0),(-1,-1),(-1,-2)],

[(0,1),(0,2),(1,2)],
[(0,1),(0,2),(-1,2)],
[(0,1),(1,1),(2,1)],
[(0,1),(-1,1),(-2,1)],

[(0,-1),(0,-2),(1,-2)],
[(0,-1),(0,-2),(-1,-2)],
[(0,-1),(1,-1),(2,-1)],
[(0,-1),(-1,-1),(-2,-1)],
]:
new_path = [(l[0]+cur[0], l[1]+cur[1]) for l in L]
if all(on_board(p) and not p in visited for p in new_path):
for solution in search(path + new_path):
yield solution

def path_to_string(path):
chars = [[' ']*(BOARD_WIDTH*2-1) for _ in range(BOARD_HEIGHT*2-1)]

for i,(x,y) in enumerate(path):
chars[2*y][2*x] = '#' if i % 3 == 0 else '+'

for i in range(len(path)-1):
(x0,y0),(x1,y1) = path[i:i+2]
chars[y0+y1][x0+x1] = '|' if x0 == x1 else '-'

return '\n'.join(''.join(row) for row in chars)

def canonize_path_string(s):
a = s
b = s[::-1]
c = '\n'.join(s.split('\n')[::-1])
d = c[::-1]

return min(a,b,c,d)

path_strings = set()
for v in VERTICES:
for path in search([v]):
path_strings.add(canonize_path_string(path_to_string(path)))

print '\n\n'.join(sorted(path_strings))


Edit: I also ran it on an 8x8 board. This took much longer and produced the following 52 solutions: http://pastebin.com/pThG6PsD

• then probably a more interesing question could be to find out for which kind of boards no solution exits, if it is true at all, for some reasonable board size. Oct 27, 2016 at 21:15
• @SeyhmusGüngören For a solution to exist on an $n \times m$ board it's necessary that $n,m > 3$ and $nm \equiv 1\ \text{(mod 3)}$. For small cases, my script shows these are sufficient. It may be possible to prove that these are sufficient for larger cases by concatenating parts of smaller solutions. Oct 27, 2016 at 21:41
• okay so this means for $4\times 11$, $6\times 11$, $7\times 11$, $8\times 11$, $9\times 11$, $10\times 11$, $11\times 11$.. etc there is no solution.. Oct 27, 2016 at 21:48
• @SeyhmusGüngören 8 x 11 and 11 x 11 may have solutions. Their products are equivalent to 1 mod 3. Oct 27, 2016 at 22:02