Search

• There are knight's tours in n × n boards with less than 9.25 n turns and 12 n crossings. • Any knight's tour in an n × n board has over 5.99 n turns and 4 n crossings. • Using a 2 × 2 formation of parallel knight moves helps reduce both turns and crossings. • A new knight's tour algorithm minimizes turns and crossings simultaneously. • Our new knight's tour algorithm can be generalized to 3D boards and similar pieces. We introduce two new metrics of "simplicity" for knight's tours: the number of turns and the number of crossings. We give a novel algorithm that produces tours with 9.25 n + O (1) turns and 12 n + O (1) crossings on an n × n board, and we show lower bounds of (6 − ϵ) n and 4 n − O (1) on the respective problems of minimizing these metrics. Hence, our algorithm achieves approximation ratios of 9.25 / 6 + o (1) and 3 + o (1). Our algorithm takes linear time and is fully parallelizable, i.e., the tour can be computed in O (n 2 / p) time using p processors in the CREW PRAM model. We generalize our techniques to rectangular boards, high-dimensional boards, symmetric tours, odd boards with a missing corner, and tours for (1 , 4) -leapers. In doing so, we show that these extensions also admit a constant approximation ratio on the minimum number of turns, and on the number of crossings in most cases. [ABSTRACT FROM AUTHOR]