Knight’s Tour in JavaScript: Solve Chessboard Pathfinding with Backtracking

♞ Knight’s Tour Algorithm in JavaScript

📌 What is the Knight’s Tour Problem?

The Knight’s Tour is a classic chessboard problem where a knight must visit every square exactly once. It uses backtracking to explore all paths.

💡 Example

Given a "5×5 chessboard", the knight moves in L-shaped steps to cover all squares.

🚀 How Does It Work?

The algorithm tries all possible moves for the knight and uses backtracking to find a solution.

• Start from an empty chessboard.
• Move the knight in all valid directions.
• Mark visited squares and continue exploring.
• If no valid move remains, backtrack to the last position.
• Continue until the knight covers all squares.

🛠️ Code Implementation

class OpenKnightTour {
  constructor(size) {
    this.board = new Array(size).fill(0).map(() => new Array(size).fill(0));
    this.size = size;
  }

  getMoves([i, j]) {
    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]
    ];
    return moves.filter(([y, x]) => y >= 0 && y < this.size && x >= 0 && x < this.size);
  }

  isComplete() {
    return !this.board.map((row) => row.includes(0)).includes(true);
  }

  solve() {
    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) {
    if (this.isComplete()) return true;
    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;
        this.board[y][x] = 0;
      }
    }
    return false;
  }

  printBoard(output = (value) => console.log(value)) {
    for (const row of this.board) {
      let string = '';
      for (const elem of row) {
        string += elem + '\t';
      }
      output(string);
    }
  }
}

export { OpenKnightTour };
  

📌 Example Usage

Let’s solve the Knight’s Tour on a "5×5 board":

import { OpenKnightTour } from './your-file.js';

const knightTour = new OpenKnightTour(5);
if (knightTour.solve()) {
  knightTour.printBoard();
} else {
  console.log("No solution found.");
}
  

⏳ Time Complexity

The worst-case complexity is "O(8ⁿ²)" due to multiple possible moves. However, heuristics like Warnsdorff’s Rule can optimize it.

📌 Where is This Used?

• Solving chess-based puzzles
• Developing AI for chess engines
• Pathfinding in robotics
• Graph traversal problems