JavaScript/Backtracking/KnightTour.js

// Wikipedia: https://en.wikipedia.org/wiki/Knight%27s_tour

class OpenKnightTour {
  constructor(size) {
    // Constructor to initialize the chessboard and size
    this.board = new Array(size).fill(0).map(() => new Array(size).fill(0))
    this.size = size
  }

  getMoves([i, j]) {
    // Helper function to get the valid moves of the knight from the current position
    const moves = [
      [i + 2, j - 1],
      [i + 2, j + 1],
      [i - 2, j - 1],
      [i - 2, j + 1],
      [i + 1, j - 2],
      [i + 1, j + 2],
      [i - 1, j - 2],
      [i - 1, j + 2]
    ]

    // Filter out moves that are within the board boundaries
    return moves.filter(
      ([y, x]) => y >= 0 && y < this.size && x >= 0 && x < this.size
    )
  }

  isComplete() {
    // Helper function to check if the board is complete
    return !this.board.map((row) => row.includes(0)).includes(true)
  }

  solve() {
    // Function to find the solution for the given board
    for (let i = 0; i < this.size; i++) {
      for (let j = 0; j < this.size; j++) {
        if (this.solveHelper([i, j], 0)) return true
      }
    }
    return false
  }

  solveHelper([i, j], curr) {
    // Helper function for the main computation
    if (this.isComplete()) return true

    // Iterate through possible moves and attempt to fill the board
    for (const [y, x] of this.getMoves([i, j])) {
      if (this.board[y][x] === 0) {
        this.board[y][x] = curr + 1
        if (this.solveHelper([y, x], curr + 1)) return true
        // Backtracking: If the solution is not found, reset the cell to 0
        this.board[y][x] = 0
      }
    }
    return false
  }

  printBoard(output = (value) => console.log(value)) {
    // Utility function to display the board
    for (const row of this.board) {
      let string = ''
      for (const elem of row) {
        string += elem + '\t'
      }
      output(string)
    }
  }
}

export { OpenKnightTour }