Knight's Tour Problem

A knight’s tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight’s move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open.

The knight’s tour problem is the mathematical problem of finding a knight’s tour. Creating a program to find a knight’s tour is a common problem given to computer science students. Variations of the knight’s tour problem involve chessboards of different sizes than the usual 8×8, as well as irregular (non-rectangular) boards.

The knight’s tour problem is an instance of the more general Hamiltonian path problem in graph theory. The problem of finding a closed knight’s tour is similarly an instance of the Hamiltonian cycle problem.

An open knight’s tour of a chessboard.

An animation of an open knight’s tour on a 5 by 5 board.

References

• trekhleb/javascript-algorithms
• Wikipedia
• GeeksForGeeks

Implementations

• Python
• JavaScript

• 1
  # TODO: Implement in Python
  

• 1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  /*
  For N>3 the time taken by this algorithm is sufficiently high
  Also it is not possible to visualise for N>6 due to stack overflow
  caused by large number of recursive calls
  */
  const N = 3;
  const board = new Array(N);
  for (let i = board.length - 1; i >= 0; i--) {
    board[i] = new Array(N);
  }
  
  for (let i = board.length - 1; i >= 0; i--) {
    for (let j = board[i].length - 1; j >= 0; j--) {
      board[i][j] = -1;
    }
  }
  
  /*
  Define the next move of the knight
  */
  const X = [2, 1, -1, -2, -2, -1, 1, 2];
  const Y = [1, 2, 2, 1, -1, -2, -2, -1];
  
  const pos = new Array(2);
  pos[0] = pos[1] = -1;
  
  function knightTour(x, y, moveNum) {
    if (moveNum === N * N) {
      return true;
    }
  
    for (let i = 0; i < 8; i++) {
      const nextX = x + X[i];
      const nextY = y + Y[i];
  
      /*
      Check if knight is still in the board
      Check that knight does not visit an already visited square
      */
      if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N && board[nextX][nextY] === -1) {
        board[nextX][nextY] = moveNum;
  
        const nextMoveNum = moveNum + 1;
        if (knightTour(nextX, nextY, nextMoveNum) === true) {
          return true;
        }
  
        logTracer.println(`No place to move from ${nextX},${nextY}: Backtrack`);
        
        board[nextX][nextY] = -1; // backtrack
        
      } else {
        
        logTracer.println(`${nextX},${nextY} is not a valid move`);
        
      }
    }
    return false;
  }
  
  board[0][0] = 0; // start from this position
  pos[0] = 0;
  pos[0] = 0;
  
  if (knightTour(0, 0, 1) === false) {
    logTracer.println('Solution does not exist');
  } else {
    logTracer.println('Solution found');
  }