Analog neuro-based approach to tiling problem using fitting function of polyominoes
Hiroshi Ninomiya, Takeshi Nakayama, Hideki Asai · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 2000
The tiling problem is a typical NP-complete problem, where the polyominoes are to be arranged without a gap on a finite checkerboard. In this study, the arrangement of l polyominoes on an m ×n checkerboard is considered. As the first step, the conventional parallel algorithm using the maximum neural network is verified. Then, the authors propose a solution procedure for the tiling problem, where the analog neural network is used in addition to the fitting function. Lastly, the proposed method and the conventional method are compared, and it is shown that the proposed method is also effective for more complex tiling problems. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 83(2): 1–10, 2000