Knight’s Tours Using a Neural Network

There was a paper in an issue of Neurocomputing that got me intrigued: it spoke of a neural network solution to the knight’s tour problem. I decided to write a quick C++ implementation to see for myself, and the results, although limited, were thoroughly fascinating.

The neural network is designed such that each legal knight’s move on the chessboard is represented by a neuron. Therefore, the network basically takes the shape of the knight’s graph over an \(n \times n\) chess board. (A knight’s graph is simply the set of all knight moves on the board)

Each neuron can be either “active” or “inactive” (output of 1 or 0). If a neuron is active, it is considered part of the solution to the knight’s tour. Once the network is started, each active neuron is configured so that it reaches a “stable” state if and only if it has exactly two neighboring neurons that are also active (otherwise, the state of the neuron changes). When the entire network is stable, a solution is obtained. The complete transition rules are as follows:

$$U_{t+1} (N_{i,j}) = U_t(N_{i,j}) + 2 – \sum_{N \in G(N_{i,j})} V_t(N)$$

$$V_{t+1} (N_{i,j}) = \left\{
\begin{array}{ll}
1 & \mbox{if}\,\, U_{t+1}(N_{i,j}) > 3\\
0 & \mbox{if}\,\, U_{t+1}(N_{i,j}) < 0\\
V_t(N_{i,j}) & \mbox{otherwise},
\end{array} \right.$$

where \(t\) represents time (incrementing in discrete intervals), \(U(N_{i,j})\) is the state of the neuron connecting square \(i\) to square \(j\), \(V(N_{i,j})\) is the output of the neuron from \(i\) to \(j\), and \(G(N_{i,j})\) is the set of “neighbors” of the neuron (all neurons that share a vertex with \(N_{i,j}\)).

Initially (at \(t = 0\)), the state of each neuron is set to 0, and the output of each neuron is set randomly to either 0 or 1. The neurons are then updated sequentially by counting squares on the chess board in row-major order and enumerating the neurons that represent knight moves out of each square.

Essentially, the network is configured to generate subgraphs of degree 2 within the knight’s graph. The set of degree-2 subgraphs naturally includes Hamiltonian circuits (re-entrant Knight’s Tours). However, there are many other solutions that would satisfy the network that are not knight’s tours. For example, the network could discover two or more small independent curcuits within the knight’s graph. In addition, there are certain cases that will cause the network to diverge (never become stable).

Knight’s Tour on an \(8 \times 8\) board:

Not a Knight’s Tour, but still a solution (can you spot the four independent circuits?):

In fact, the probability of obtaining a knight’s tour on an \(n \times n\) board virtually vanishes as n grows larger. Takefuji, at the time of his publication, only obtained solutions for \(n < 20\). Parberry was able to obtain a single knight's tour out of 40,000 trials for \(n = 26\). I obtained one knight's tour out of about 200,000 trials for \(n = 28\) (three days' worth of calculation on my Pentium IV). Parberry wisely asserts that attempting to find a knight's tour for \(n > 30\) using this method would be futile.

Implementation

Knight's tour screen shot
My implementation of this algorithm takes the shape of an application for Windows (although it’s perfectly runnable under Linux using wine). Several key features of the program include support for arbitrary rectangular chess boards, as well as
statistical records of trials performed.

Download the application. (Or browse the source code on GitHub)

As seen in the screenshot, the program allows you to change the width and height of the chess board. You can then adjust the number of trials to perform. Click the Start button to begin the calculation. The program will then display its progress in the statistics window on the right, showing the number of knight’s tours found, number of non-knight’s tours found, and number of divergent patterns. By default, the program draws the chess board only when a knight’s tour has been found. However, if you enable the Display All check box, the program will draw all solutions it finds.

Notable Finds

Symmetric 10 x 3 knight’s tour
Symmetric 14 x 3 knight’s tour
24 x 24 knight’s tour (2 hours cpu time)
26 x 26 knight’s tour (8 hours cpu time)
28 x 28 knight’s tour (50 hours cpu time)

Undoubtedly, knight’s tours for n > 28 can easily be found using simpler combinatorial algorithms, which seems to make this neural network solution for the knight’s tour problem less than practical. However, one cannot deny the inherent elegance in this kind of solution, which is what made it so interesting to investigate.

References

  • I. Parberry. Scalability of a neural network for the knight’s tour problem. Neurocomputing, 12:19-34, 1996.
  • Y. Takefuji and K. C. Lee. Neural network computing for knight’s tour problems. Neurocomputing, 4(5):249-254, 1992.
Share this article:
  • Facebook
  • LinkedIn
  • Reddit
  • Twitter

14 thoughts on “Knight’s Tours Using a Neural Network

  1. Pierre Charland

    Interesting program!
    It would be nice if it could stop at each solution (or save each solution), and if it could tell the number of close loops. May be each loop could be of a different color.
    (if I set the #trials to 1000 or more, it does only one trial)

    Reply
  2. Pierre Charland

    Try the program on a 3×3.
    It find an hamiltonian path!
    (wrong since the center cell is unattainable)

    Reply
  3. db

    Ha! So it does find a “solution” for a 3×3 board… I guess I never tested that case. I’ll have to limit the width and height to 4, then!

    Reply
  4. Pingback: One heck of ... - CodeCall Programming Forum

  5. alphachap

    I tried the downloaded application, but got access violation at address .. in module ‘KERNELBASE.dll’ ..
    Had to do Ctrl-Alt-Del to stop the process.

    Reply
  6. Michael

    Hey I would like to use your source code for a project. Apparently you would like to keep track of who uses your code, so could you please email me the credentials needed to download it? This would be very much appreciated!

    P.S. This is a very cool program!

    Reply
  7. Craig

    Interesting read!

    In 1988, for a computer science assignment in high school, I wrote a program in BASIC on my IBM JX which worked out a solution to the knight’s tour problem using the neural network method you describe above.

    Of course, I didn’t know it was the neural network method at the time. It was simply the solution I arrived at after thinking about it for a couple of days.

    Also, my algorithm was very different, although it calculated the same thing. And the solution to an 8×8 board took many hours to complete, which was probably more to do with my inefficient coding than the technology of the day :-)

    http://en.wikipedia.org/wiki/IBM_JX

    Reply
  8. CHC

    And to bring us to the present day, I am now working in my studio on a watercolor project involving a knight’s tour on a 6×6 grid, where the alphabet (and arabic numerals) are ordered a sequence of knight jumps, with the color of each square changing slightly from jump to jump. I did not use a neural net to find the tour, but got a hint from a website to “find the square that is closest to the exterior” of the grid and work your way around.

    PS Sort of miss the old format.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>