Knight’s Tour

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.

Installation

Install Knight’s Tour as a RubyGem from GitHub:

$ sudo gem install tuomas-knights_tour --source http://gems.github.com

The program is compatible with Ruby 1.9.1.

Usage

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

Contacting

Please send feedback by email to Tuomas Kareinen < tkareine (at) gmail (dot) com >.

Knight’s Tour

Installation

Usage

Contacting

Legal notes