5
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Where does it start? And, do you mean "every field once"? Is it possible to move $a1 \to a2 \to b2 \to b3$? $\endgroup$ – user202729 Oct 16 '16 at 14:49
  • $\begingroup$ @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. $\endgroup$ – Peter Oct 16 '16 at 15:18
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 17 '16 at 11:53
  • $\begingroup$ 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? $\endgroup$ – McLinux Oct 23 '16 at 15:06
  • $\begingroup$ @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”. :-) $\endgroup$ – Alex Ravsky Oct 25 '16 at 7:25
12
+50
$\begingroup$

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:

enter image description here

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – bof Oct 25 '16 at 9:39
  • $\begingroup$ @bof Yes, of course. $\endgroup$ – Alex Ravsky Oct 25 '16 at 9:41
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Seyhmus Güngören Oct 27 '16 at 21:15
  • $\begingroup$ @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. $\endgroup$ – cardboard_box Oct 27 '16 at 21:41
  • $\begingroup$ 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.. $\endgroup$ – Seyhmus Güngören Oct 27 '16 at 21:48
  • $\begingroup$ @SeyhmusGüngören 8 x 11 and 11 x 11 may have solutions. Their products are equivalent to 1 mod 3. $\endgroup$ – cardboard_box Oct 27 '16 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.