摘要：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.5n+O(1) turns and 13n+O(1) crossings on a nÃ- n board, and we show lower bounds of (6-ε)n and 4n-O(1) on the respective problems of minimizing these metrics. Hence, our algorithm achieves approximation ratios of 19/12+o(1) and 13/4+o(1). 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.
