The classic Knight’s Tour Problem asks for a sequence of knight moves in an n×n chess board that allows the knight to visit every square exactly once and return to the starting position. There is a long history of algorithms for producing knight tours. However, most of them produce complex tours. We consider the problem of finding knight’s tours minimizing two metrics of complexity: the number of turns and the number of crossings. A turn is when two consecutive knight moves in the tour go in different directions (i.e., when the three cells involved are not collinear); a crossing is when the line segment connecting the cells of two knight moves intersect. To the best of our knowledge, these metrics are new in this context, but they are often studied in geometric contexts and, in the case of crossings, in graph drawing.
Authors: Juan Jose Besa, Timothy Johnson, Nil Mamano, and Martha C. Osegueda