This project implements a solution to the Knight's Tour problem using Warnsdorff's rule, a heuristic following these principles:
- The knight is moved to a square from which the knight will have the fewest onward moves. The idea is to always move the knight to a position where there are fewer possibilities for future moves, ensuring that no squares are missed.
In addition to the basic heuristic, there's an optimized solution that includes a tie-breaking mechanism:
-
Accessibility: For each potential move, we calculate the accessibility (the number of valid onward moves possible from that position). We then select the move with the highest accessibility, preserving more options for future moves.
-
Random Selection: If multiple moves have the same level of accessibility, the algorithm randomly selects from these tied moves.
-
Moving Your Knight: Click on any square within the GUI to place your knight's starting position
-
Next Button: Moves the knight to the next optimal position based on the selected heuristic, allowing you to step through the tour one move at a time.
-
Run Button: Automatically visualizes the entire Knight's Tour, displaying each move sequentially. Each visited square will be numbered to indicate the order in which the knight made its stops.
-
Stop Button: Stops the visualization