Class ChessHorseOne

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

The Knight's Tour (First Solution)

This class calculates a single valid path that a Knight can take to visit every square on an N × N chessboard exactly once. It employs a Backtracking algorithm designed to halt the execution tree immediately upon discovering the first valid topological path.

Complexity

  • Time Complexity: O(8N²) - The theoretical worst-case explores 8 branching possibilities at each depth level. However, the early termination mechanism drastically reduces the practical execution time if a solution exists.
  • 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
    ChessHorseOne(int boardSize, int startingX, int startingY)
    Initializes the chessboard and sets up the starting position.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    hasFoundSolution()
    Retrieves the execution status to determine if a valid path was discovered.
    void
    solve()
    Triggers the backtracking execution to find the first valid tour.

    Methods inherited from class Object

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

  • Constructor Details

    • ChessHorseOne

      public ChessHorseOne(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 the first valid tour.

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

    • hasFoundSolution

      public boolean hasFoundSolution()
      Retrieves the execution status to determine if a valid path was discovered.
      Returns:
      true if a solution exists; false otherwise.