Class ChessHorseSimpleHeuristic

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

Knight's Tour

Attempts to move a knight across every square of a chessboard exactly once. Unlike Warnsdorff's Rule, this implementation uses a "Naive Heuristic": it simply picks the first available legal jump it evaluates, without looking ahead or weighing its options.

Educational Purpose

This class serves as a counter-example to demonstrate that a Greedy Algorithm is only as good as its heuristic. Because it blindly takes the first valid move, it almost always traps itself in a dead end very quickly, failing to complete even simple boards.

Author:
vicegd

  • Constructor Details

    • ChessHorseSimpleHeuristic

      public ChessHorseSimpleHeuristic(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 using a naive first-fit greedy approach.
      Parameters:
      startPos - Initial position [x, y]
      Returns:
      true if the knight successfully visited every square, false if it hit a dead end.