Skip to main content

Knight Terror

Investigating the commonly posed CS problem of calculating a "Knight's Tour".


Sean J McKiernan
(mekire)

Investigating the commonly posed CS problem of calculating a "Knight's Tour".



Calculates a knight's tour using the Warnsdorff algorithm.
You can also put it on a plain brute force mode to illustrate
how utterly ineffective this approach is.

If you are not familiar with Warnsdorff's algorithm or with the problem of finding a Knight's Tour in general please see the wikipedia page on this subject.
http://en.wikipedia.org/wiki/Knight's_tour

Controls:
Mouse: Place knight, click buttons

HotKeys:
Space: Start
Enter: Reset
+ : Increase FPS
- : Decrease FPS
w : Toggle between Warnsdorff/Brute
# : Toggle showing path numbers on/off
c : Toggle continuous solution mode on/off
r : Replay current tour
n: Pop the stack and find next tour
Esc : Quit

Note:
Searching for a closed tour specifically is not yet implemented.
The tour you find may be closed but you are much more likely to find open tours.

Changes

2d 783 mekire 11 knighttour 1

Links

Home Page
http://code.google.com/p/knight-terror/

Releases

Knight Terror 0.01 — 19 Dec, 2011

Pygame.org account Comments

  • William Manire 2012-02-19 05:27

    Wow, this demo was excellent. The script ran perfectly right out of the zip file on my linux notebook. I enjoyed playing with the framerate and comparing the two different algorithms. These kinds of demonstrations always show the value of a well thought out algorithm. I hope you consider doing examples of other algorithms like this one in the future. Perhaps a merge sort would be interesting?

    Mekire 2012-03-03 00:22

     Thank you.  Glad you enjoyed it.

    -Mek