A program that attempts to find a solution to the Knight’s Tour problem. I was inspired to do this by finding a Python implementation.
The program’s algorithm is a recursive backtracking search that returns the first solution to the problem (if the algorithm finds one). It utilizes Warnsdorff’s heuristics to avoid dead ends, making the search faster in general.
Install Knight’s Tour as a RubyGem from Gemcutter:
$ sudo gem install knights_tour --source http://gemcutter.org
The program is compatible with both Ruby 1.8 and 1.9.
In the command line, run the program by entering
$ knights_tour
The command attempts to solve the problem on a board of size 8x8, the knight located initially at position 0,0 (the top-left corner). If the program finds a solution, it displays a result similar to the following:
+---+---+---+---+---+---+---+---+ | 1| 62| 13| 36| 3| 38| 31| 28| +---+---+---+---+---+---+---+---+ | 14| 35| 2| 63| 32| 29| 4| 39| +---+---+---+---+---+---+---+---+ | 61| 12| 59| 34| 37| 42| 27| 30| +---+---+---+---+---+---+---+---+ | 50| 15| 64| 43| 58| 33| 40| 5| +---+---+---+---+---+---+---+---+ | 11| 60| 49| 54| 41| 24| 45| 26| +---+---+---+---+---+---+---+---+ | 16| 51| 18| 57| 44| 55| 6| 23| +---+---+---+---+---+---+---+---+ | 19| 10| 53| 48| 21| 8| 25| 46| +---+---+---+---+---+---+---+---+ | 52| 17| 20| 9| 56| 47| 22| 7| +---+---+---+---+---+---+---+---+
The command above is the same as invoking the program with
$ knights_tour -s 0,0 8,8
The size of the board and the start position of the knight are configurable, however. For all the options, see
$ knights_tour -h
Please send feedback by email to Tuomas Kareinen < tkareine (at) gmail (dot) com >.
Copyright © 2008-2009 Tuomas Kareinen. See MIT-LICENSE.txt in this directory.