Finding knight´s tours on an M×N chessboard with O(MN) hysteresis McCulloch-Pitts neurons

Author

Lee, Kuo-Chun ; Takefuji, Yoshiyasu

Author_Institution

R&D Development, Cirrus Logic Inc., Fremont, CA, USA

Volume

24

Issue

2

fYear

1994

fDate

2/1/1994 12:00:00 AM

Firstpage

300

Lastpage

306

Abstract

How can a knight be moved on a chessboard so that the knight visits each square once and only once and goes back to the starting square? The earliest serious attempt to find a knight´s tour on the chessboard was made by L. Euler in 1759 [1]. In this correspondence, a parallel algorithm based on the hysteresis McCulloch-Pitts neurons is proposed to solve the knight´s tour problem. The relation between the traveling salesman problem and the knight´s tour problem is also discussed. A large number of simulation runs were performed to investigate the behavior of the hysteresis McCulloch-Pitts neural model. The purpose of this correspondence is to present a case study-how to successfully represent the combinatorial optimization problems by means of neural network

Keywords

combinatorial mathematics; hysteresis; neural nets; operations research; optimisation; parallel algorithms; M×N chessboard; O(MN) hysteresis McCulloch-Pitts neurons; chessboard; combinatorial optimization; knight´s tours; neural network; parallel algorithm; traveling salesman problem; Biology computing; Constraint theory; Convergence; Equations; Hysteresis; Mathematical model; Neural networks; Neurons; Planarization; Switches;

fLanguage

English

Journal_Title

Systems, Man and Cybernetics, IEEE Transactions on

Publisher

ieee

ISSN

0018-9472

Type

jour

DOI

10.1109/21.281427

Filename

281427