A neural network algorithm for the no-three-in-line problem : NOTES

notes-a-neural-network-algorithm-for-the-no-three-in-line-problem.md

This is a nice paper, where Tsuchiya and Takefuji discuss how they use N x N hysteresis McCulloch-Pitts neurons as processing elements for the no-three-in-line problem. They discover solutions for up to N = 25.

Literature review

For N > 20, many of the solutions to the no-three-in-line problem have been solved by a computer search. Rotation and reflection symmetry are used to reduce the search space.

Hopfield and Tank proposed the first neural-network approach to optimization problems. They applied sigmoid neural network to the travelling salesman problem. Szu used McCulloch-Pitts neural network for the same problem. To suppress the oscillatory behavior, the hysteresis neuron model has been introduced.

Neural representation

The hysterisis McCulloch-Pitts neuron is a neuron that fires at after a certain input voltage, but suppressed the firing after the input voltage crosses a certain higher threshold. Tsuchiya and Takefuji use an N x N neural array, where the output of the i, jth neuron indicates whether a point is located there. They write the motion equation, taking into account the row, column, and other directional constraints., i.e., they equation discourages other neurons to fire if two neurons are already firing in the same row, column, etc., and encourage other neurons to fire if only one neuron is firing in the same row, column, etc. This is peformed iteratively.

Results

They experiment on a Macintosh PowerBook 170 and a DEC 3100 computer! "It took about 10 minutes (!) to obtain the solution on N = 25 in the DEC machine." Running the neural network program takes $O(N^2)$ time on a sequential machine, and about $O(1)$ time on a parallel machine with $N^2$ processing elements.

notes-a-neural-network-algorithm-for-the-no-three-in-line-problem.pdf