Class ChessHorseAll

java.lang.Object
topics.backtracking.knighttour.ChessHorseAll
public class ChessHorseAll extends Object

The Knight's Tour (All Solutions)

This class calculates all possible paths (both open and closed) that a Knight can take to visit every square on an N × N chessboard exactly once. It employs a Backtracking algorithm to explore the state space tree systemically.

Complexity

  • Time Complexity: O(8N²) - In the worst-case scenario, the algorithm explores 8 branching possibilities at each of the N² depth levels.
  • Space Complexity: O(N²) - Required for storing the board matrix and the maximum depth of the JVM call stack.
Author:
vicegd

  • Constructor Summary

    Constructors
    Constructor
    Description
    ChessHorseAll(int boardSize, int startingX, int startingY)
    Initializes the chessboard and sets up the starting position.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    getSolutionCount()
    Retrieves the total number of solutions discovered after the search completes.
    void
    solve()
    Triggers the backtracking execution to find all valid tours.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • ChessHorseAll

      public ChessHorseAll(int boardSize, int startingX, int startingY)
      Initializes the chessboard and sets up the starting position.
      Parameters:
      boardSize - The size of the side of the square board (N × N).
      startingX - The initial horizontal coordinate (0-indexed).
      startingY - The initial vertical coordinate (0-indexed).

  • Method Details

    • solve

      public void solve()
      Triggers the backtracking execution to find all valid tours.

      The search begins from the second jump, as the first jump is already placed at the starting coordinates.

    • getSolutionCount

      public int getSolutionCount()
      Retrieves the total number of solutions discovered after the search completes.
      Returns:
      The integer count of valid Knight's Tours.