Generalized Knight's Tour Problem and Its Solutions Algorithm
Sen Bai, Xiaofeng Liao, QU Xiao-hong, Yijun Liu · 2006
Knight's tour matrix, the solution of knight's tour problem (KTP), can be applied to digital image information security. Inspired by the solution of KTP and the require of information security, in this paper, the KTP is generalized to m-dimensional space to get generalized knight's tour problem (GKTP). We give the GKTP's mathematic definitions and investigate its solutions algorithm. When (x1, x2,middotmiddot,middot, xm) is a beginning point of the generalized m-dimensional knight want to visit, by focusing on its move, we show that nmchessboard does not have a knight tour if n and x1+x2+middotmiddotmiddotxmare odd. Based on this and minimal outlet number, an intelligence algorithm is proposed to find solutions of the m-dimensional GKTP. The proposed algorithm can also be applied to generalized 2-dimensional [a1, a2]-knight's tour problem. The experimental results show that presented algorithm is able to find quickly the generalized knight's tour matrix (KTM), namely the solutions of GKTP