Knight's Tour using a Neural Network

I was looking at the knights tour problem and decided to have a go at implementing it in python using a neural network to find solutions.

The general explanation of the method can be found on Wikipedia

While I think I have implemented it correctly (I can't see anything else that is wrong), it doesn't work, it updates a few links, removing the edges where the connecting vertex has a degree more than two, but it doesn't converge on the solution.

I was wondering if anyone had any ideas on what I have implemented incorrectly (Sorry about the horribl开发者_运维知识库e code).

EDIT

Working code can be found at GitHub https://github.com/Yacoby/KnightsTour

You can't update the neurons in place. Since U[t+1] depends on U[t] and V[t], if you have already updated V the calculation for U will be wrong

I think you should split the update into two phases update_state and update_output, so all the U are updated and then all the V

    for n in neurons:
        n.update_state()
    for n in neurons:
        n.update_output()

First impression is that you only have one buffer for the board. I'm basing this on the fact that I don't see any buffer swaps between iterations - I haven't looked that closely and may easily be wrong.

If you modify a single buffer in place, when you do the neighbour counts, you base them on a partly modified board - not the board you had at the start.

After looking over your code, I think your explanation for the formula you used may be incorrect. You say that when updating the state you add four rather than two and subtract the output of the neuron itself. It looks to me like you're subtracting the output of the neuron itself twice. Your code which finds neighbors does not appear to distinguish between neighbors of the neuron and the neuron itself, and you run this code twice- once for each vertex.

Tests on my own code seem to confirm this. Convergence rates drastically improve when I subtract the neuron's own output twice rather than once.