Class ChessHorse

java.lang.Object
topics.greedy.knighttour.ChessHorse
public class ChessHorse extends Object

Knight's Tour (Warnsdorff's Heuristic)

Attempts to move a knight across every square of a chessboard exactly once. It uses Warnsdorff's Rule as its greedy heuristic: always choose the next jump that has the fewest onward accessible unvisited squares.

The Greedy Trap

While Warnsdorff's heuristic is extremely fast and works magically well for many board sizes and starting positions, it is a purely Greedy approach and does NOT guarantee a solution in all theoretically solvable cases (it can hit dead ends). Absolute guarantees require backtracking (Divide invalid input: '&' Conquer / DFS).

Author:
vicegd

  • Constructor Details

    • ChessHorse

      public ChessHorse(int n)
      Constructs the chessboard.
      Parameters:
      n - Dimension of the board.

  • Method Details

    • solveTour

      public boolean solveTour(int[] startPos)
      Attempts to complete the Knight's Tour starting from a specific position.
      Parameters:
      startPos - Initial position [x, y]
      Returns:
      true if the knight successfully visited every square, false if it hit a dead end.