A chess knight's moves

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:

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