Yacoby's Wanderings | Knights Tour

Knights Tour using a Neural Network

When I first encountered the idea that solutions to the knight's tour problem could be found using Neural Networks I was intrigued. I hadn't done anything to speak of with neural networks, so decided to write a quick implementation.

The only thing that I found was that either I made a mistake in my code somewhere, or the formula was wrong. The suggested function was

$U_{t+1} (N_{i,j}) = U_t(N_{i,j}) + 2 - \sum_{N \in G(N_{i,j})} V_t(N)\\<br />V_{t+1} (N_{i,j}) = \left\{\\\begin{array}{ll}\\1 & \mbox{if}\,\, U_{t+1}(N_{i,j}) > 3\\<br />0 & \mbox{if}\,\, U_{t+1}(N_{i,j}) < 0\\V_t(N_{i,j}) & \mbox{otherwise}\\\end{array} \right.$

where t represents discrete intervals of time, 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 neighbours of the neuron.

I only managed to get it to produce valid tours by altering it slightly, changing the constant 2 to 4 and subtracting not only the sum of the output of the neighbours, but also the output of the neuron itself.

$U_{t+1} (N_{i,j}) = U_t(N_{i,j}) + 4 - \sum_{N \in G(N_{i,j})} V_t(N) - V_t(N_{i,j})<br /><br />$

While there is a faster implementation out there, this implementation is (IMHO) far more readable. My implementation is written in Python (2.6) and using PyGame for its graphical output. While not great code, it does what it should.

Return will cause the program state to be reset, while space will pause the updating of the neural network and update the neural network once (space can then be repeatedly pressed to update the network by one).

The code can be found on GitHub