
Task
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. Note that it is not a requirement that the tour be "closed"; that is, the knight need not end within a single move of its start position.

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 according 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



Related tasks
 A* search algorithm
 N-queens problem
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


import algorithm, options, random, parseutils, strutils, strformat
 
type
  Board[N: static Positive] = array[N, array[N, int]]
  Move = tuple[x, y: int]
  MoveList = array[8, Move]
  MoveIndexes = array[8, int]
 
const Moves: MoveList = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
 
proc `$`(board: Board): string =
  ## Display the board.
  let size = len($(board.N * board.N)) + 1
  for row in board:
    for val in row:
      stdout.write ($val).align(size)
    echo ""
 
proc sortedMoves(board: Board; x, y: int): MoveIndexes =
  ## Return the list of moves sorted by count of possible moves.
 
  var counts: array[8, tuple[value, index: int]]
  for i, d1 in Moves:
    var count = 0
    for d2 in Moves:
      let x2 = x + d1.x + d2.x
      let y2 = y + d1.y + d2.y
      if x2 in 0..<board.N and y2 in 0..<board.N and board[y2][x2] == 0:
        inc count
    counts[i] = (count, i)
 
  counts.shuffle()  # Shuffle to randomly break ties.
  counts.sort()     # Lexicographic sort.
 
  for i, count in counts:
    result[i] = count.index
 
 
proc knightTour[N: static Positive](start: string): Option[Board[N]] =
  ## Return the knight tour for a board of size N x N and the starting
  ## position "start.
  ## If no solution is found, return "node" else return "some".
 
  # Initialize the board with the starting position.
  var board: Board[N]
  var startx, starty: int
  startx = ord(start[0]) - ord('a')
  if startx notin 0..<N:
    raise newException(ValueError, "wrong column.")
  if parseInt(start, starty, 1) != start.len - 1 or starty notin 1..N:
    raise newException(ValueError, "wrong line.")
  starty = N - starty
  board[starty][startx] = 1
 
  type OrderItem = tuple[x, y, idx: int; mi: MoveIndexes]
  var order: array[N * N, OrderItem]
  order[0] = (startx, starty, 0, board.sortedMoves(startx, starty))
 
  # Search a tour.
  var n = 0
  while n < N * N - 1:
    let x = order[n].x
    let y = order[n].y
    var ok = false
 
    for i in order[n].idx..7:
      let d = Moves[order[n].mi[i]]
      if x + d.x notin 0..<N  or y + d.y notin 0..<N: continue
      if board[y + d.y][x + d.x] == 0:
        order[n].idx = i + 1
        inc n
        board[y + d.y][x + d.x] = n + 1
        order[n] = (x + d.x, y + d.y, 0, board.sortedMoves(x + d.x, y + d.y))
        ok = true
        break
 
    if not ok:
      # Failed: backtrack.
      echo "backtrack"
      board[y][x] = 0
      dec n
      if n < 0: return none(Board[N])   # No solution found.
 
  result = some(board)
 
 
proc run[N: static Positive](start: string) =
  ## Run the algorithm and display the result.
  let result = knightTour[N](start)
  echo &"Board size: {N}x{N}, starting position: {start}."
  if result.isSome(): echo result.get()
  else: echo "No solution found.\n"
 
 
when isMainModule:
 
  randomize()
 
  run[5]("c3")
  #run[5]("c4")  # No solution, so very slow compared to other cases.
  run[8]("b5")
  run[31]("a1")