Knight's tour

Problem: you have a standard 8x8 chessboard, empty but for a single knight on some square. Your task is to emit a series of legal knight moves that result in the knight visiting every square on the chessboard exactly once.

Input and output may be textual or graphical, according to the conventions of the programming environment. If textual, squares should be indicated in Algebraic Notation. The output should indicate the order in which the knight visits the squares, starting with the initial position. The form of the output may be a diagram of the board with the squares numbered ordering to visitation sequence, or a textual list of algebraic coordinates in order, or even an actual animation of the knight moving around the chessboard.

Input: starting square Output: move sequence

Cf.

N-queens problem

Python

Knights tour using Warnsdorffs algorithm <lang python>import copy

boardsize=6 _kmoves = ((2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1))

def chess2index(chess, boardsize=boardsize):

   'Convert Algebraic chess notation to internal index format'
   chess = chess.strip().lower()
   x = ord(chess[0]) - ord('a')
   y = boardsize - int(chess[1:])
   return (x, y)

def boardstring(board, boardsize=boardsize):

   r = range(boardsize)
   lines = 
   for y in r:
       lines += '\n' + ','.join('%2i' % board[(x,y)] if board[(x,y)] else '  '
                                for x in r)
   return lines

def knightmoves(board, P, boardsize=boardsize):

   Px, Py = P
   kmoves = set((Px+x, Py+y) for x,y in _kmoves)
   kmoves = set( (x,y)
                 for x,y in kmoves
                 if 0 <= x < boardsize
                    and 0 <= y < boardsize
                    and not board[(x,y)] )
   return kmoves

def accessibility(board, P, boardsize=boardsize):

   knightmoves(board, P, boardsize=boardsize)
   access = []
   brd = copy.deepcopy(board)
   for pos in knightmoves(board, P, boardsize=boardsize):
       brd[pos] = -1
       access.append( (len(knightmoves(brd, pos, boardsize=boardsize)), pos) )
       brd[pos] = 0
   return access

def knights_tour(start, boardsize=boardsize, _debug=False):

   board = {(x,y):0 for x in range(boardsize) for y in range(boardsize)}
   move = 1
   P = chess2index(start, boardsize)
   board[P] = move
   move += 1
   if _debug:
       print(boardstring(board, boardsize=boardsize))
   while move <= len(board):
       P = min(accessibility(board, P, boardsize))[1]
       board[P] = move
       move += 1
       if _debug:
           print(boardstring(board, boardsize=boardsize))
           input('\n%2i next: ' % move)
   return board

if __name__ == '__main__':

   while 1:
       boardsize = int(input('\nboardsize: '))
       if boardsize < 5:
           continue
       start = input('Start position: ')
       board = knights_tour(start, boardsize)
       print(boardstring(board, boardsize=boardsize))</lang>

Sample runs

boardsize: 5
Start position: c3

19,12,17, 6,21
 2, 7,20,11,16
13,18, 1,22, 5
 8, 3,24,15,10
25,14, 9, 4,23

boardsize: 8
Start position: h8

38,41,18, 3,22,27,16, 1
19, 4,39,42,17, 2,23,26
40,37,54,21,52,25,28,15
 5,20,43,56,59,30,51,24
36,55,58,53,44,63,14,29
 9, 6,45,62,57,60,31,50
46,35, 8,11,48,33,64,13
 7,10,47,34,61,12,49,32

boardsize: 10
Start position: e6

29, 4,57,24,73, 6,95,10,75, 8
58,23,28, 5,94,25,74, 7,100,11
 3,30,65,56,27,72,99,96, 9,76
22,59, 2,63,68,93,26,81,12,97
31,64,55,66, 1,82,71,98,77,80
54,21,60,69,62,67,92,79,88,13
49,32,53,46,83,70,87,42,91,78
20,35,48,61,52,45,84,89,14,41
33,50,37,18,47,86,39,16,43,90
36,19,34,51,38,17,44,85,40,15