2026-07-27T17:10:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12765 2024-03-06T10:49:08Z ddc:004 open_access

Taming the Knight’s Tour: Minimizing Turns and Crossings Besa, Juan Jose Johnson, Timothy Mamano, Nil Osegueda, Martha C. Graph Drawing Chess Hamiltonian Cycle Approximation Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Juan Jose Besa and Timothy Johnson and Nil Mamano and Martha C. Osegueda 2020 Is Part Of LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2021.4 urn:nbn:de:0030-drops-127654 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.4 eng https://creativecommons.org/licenses/by/3.0/legalcode