A chess knight's moves

Question

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?

Answer 1

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:

Answer 2

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