Find a sequence of moves for a knight on an 8 x 8 chessboard that visits every square exactly once.

Hint

Place the "Knight" (a chess piece) at the top-left corner. From the Knight's current position, check all the possible moves it can make on the chessboard. For each possible move, if the move is valid (within the board boundaries):

# Python implementation


def valid(board, x, y):
  n = len(board)
  return x >= 0 and x < n and y >= 0 and y < n and board[x][y] == -1

def solve(board, x, y, move):
  M = [[-2, -1],[-2, 1],[-1, -2],[-1, 2],[1, -2],[1, 2],[2, -1],[2, 1]]
  n = len(board)

  if move == n * n:
    return True
  
  for m in M:
    next_x = x + m[0]
    next_y = y + m[1]

    if valid(board, next_x, next_y):
      board[next_x][next_y] = move

      if solve(board, next_x, next_y, move + 1):
        return True
      
      board[next_x][next_y] = -1
  
  return False

N = 8
board = [[-1 for _ in range(N)] for _ in range(N)]
board[0][0] = 0

if solve(board, 0, 0, 1):
  print(board)
else:
  print("Solution does not exist")

// Javascript implementation

function valid(board, x, y) {
  const n = board.length;
  return (x >= 0 && x < n && y >= 0 && y < n && board[x][y] == -1);
}

function solve(board, x, y, move) {
  const MOVE = [[-2, -1],[-2, 1],[-1, -2],[-1, 2],[1, -2],[1, 2],[2, -1],[2, 1]];
  const n = board.length;

  if (move == n * n) {
    return true;
  }

  for (let m of MOVE) {
    const next_x = x + m[0];
    const next_y = y + m[1];
    
    if (valid(board, next_x, next_y)) {
      board[next_x][next_y] = move;
      
      if (solve(board, next_x, next_y, move + 1)) {
        return true;
      }
      
      board[next_x][next_y] = -1;
    }
  }
  
  return false;
}

const N = 8;
const board = new Array(N);

for (let i = 0; i < board.length; i++) {
  board[i] = Array(N).fill(-1);
}

board[0][0] = 0;

if (solve(board, 0, 0, 1)) {
  console.log(board);
} else {
  console.log("Solution does not exist");
}

The Knight's tour problem

Hint