README.md

♞ Knight's Tour Visualization

A heuristic-driven tour completed by the program

About

This program visualizes and solves the Knight's tour problem in three ways using Java Swing. Check out the Live Demo on Replit.

"A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once." - Wikipedia

🎮 Manual Version

This version enables a user to control the knight to make a full tour based on the automatically generated suggestion and their intuition.

The knight's tour is controlled by the user

✈️ Heuristic Version

This version implements Warnsdorff's heuristic to complete a full tour automatically starting from each square on the chessboard.

"The knight is moved so that it always proceeds to the square from which the knight will have the fewest onward moves" - Wikipedia

🚀 Optimized Heuristic Version

This version implements the heuristic mentioned above, but when there are two or more choices for which the number of onward moves is equal, the program decides what square to choose by looking ahead to those choices.

Run

1. Navigate to the build directory

$ cd out/production/knights-tour

2. Run the program

   a. Manual version

   $ java Main
   

   b. Heuristic-driven version

   $ java Heuristic
   

   c. Optimized heuristic-driven version

   $ java OptimizedHeuristic
   

🏆 Stats

The result that I have after running the three versions of the program:

Version	Number of Full Tours
Manual	(You can try it yourself!)
Heuristic	63
Optimized	64

License

GNU GPLv3