The 2018 International Collegiate Programming Contest (ICPC) had a very hard problem which is of interest to mathematicians. The problem was proposed by super-coder Derek Kisman. Here is the problem as it was presented at the contest.
Problem J. Uncrossed Knight’s Tour. A well-known puzzle is to “tour” all the squares of an 8 × 8 chessboard using a knight, which is a piece that can move only by jumping one square in one direction and two squares in an orthogonal direction. The knight must visit every square of the chessboard, without repeats, and then return to its starting square. There are many ways to do this, and the chessboard size is manageable, so it is a reasonable puzzle for a human to solve.
However, you have access to a computer, and some coding skills! So, we will give you a harder version of this problem on a rectangular m × n chessboard with an additional constraint: the knight may never cross its own path. If you imagine its path consisting of straight line segments connecting the centers of squares it jumps between, these segments must form a simple polygon; that is, no two segments intersect or touch, except that consecutive segments touch at their common end point. This constraint makes it impossible to visit every square, so instead you must maximize the number of squares the knight visits. We keep the constraint that the knight must return to its starting square. Figure J.1 shows an optimal solution for the first sample input, a 6 × 6 board.
The input consists of a single line containing two integers m (1 ≤ m ≤ 8) and n (1 ≤ n ≤ 1015), giving the dimensions of the rectangular chessboard.
Mathematicians know many things about knight tours on a standard 8 × 8 chessboard. But one of the limits in this puzzle is so huge, that the answer to this computational puzzle constitutes a new mathematical discovery. Unsurprisingly, no one solved this puzzle during the contest. A well-written solution summary is available on the ICPC website. The solution requires dynamic programming and a realization that tours have to have repeating patterns.
Since no one solved this problem during the competition, it is useful that, in addition to the solution summary, Derek posted his innovative code online. The two figures below (courtesy of Derek Kisman) show his answer for the longest closed tour on a 6 × 24 board and the longest open tour on a 6 × 26 board.
Derek got interested in uncrossed knight’s tours after reading my blog post, 2014 Math Festival in Moscow, where I presented the following problem given at that festival to 7th graders.
Problem. Inside a 5 × 8 rectangle, Bart draws closed paths that follow diagonals of 1 × 2 rectangles. Find the longest possible path.
The 2014 Math Festival organizers offered an extra point for every diagonal on top of 16. It is funny that the organizers obfuscated that it is useless to try and find 17 diagonals, as the number of diagonals has to be even. The official solution, shown below, had 24 diagonals.
In the solution booklet, the organizers mentioned that they did not know the best answer to their own question. They hoped that the longest possible path matched their official solution.
In Derek’s notation, the above problem is equivalent to finding the largest uncrossed knight’s closed tour on a 6 × 9 grid. And Derek proved that, indeed, 24 is the largest tour. While proving this, he also calculated the answer for gazillions of other boards.
We can go further: beyond gazillions. Let’s consider what happens on m × n boards, where m is fixed, and n is astronomically large. Suppose fm(n) is the largest size of an uncrossed knight’s closed tour on the m × n board and gm(n) is the largest size of an uncrossed open tour.
The answer has repeating patterns everywhere except around the ends of the board. We would expect that the number of possible repeating patterns is finite. Moreover, for large boards, only the densest patterns would appear. This means that asymptotically, both functions f and g are linear functions of n. On top of that, as each pattern is periodic, the behavior at the ends of the long boards should become periodic as well. Hence, the difference functions of f and g for fixed m would eventually become periodic. (Here, the f’s difference function, which I denote D(fm) is defined as follows: D(fm)(n) = fm(n+1) – fm(n).)
That means we can solve a more difficult problem. We do not need the limits for n. It should be possible to calculate these functions for a given m and any n (even if n is way more than a gazillion). I am being over-optimistic here. First, we need some mathematical theory to find the bounds for where the periodic behavior has to start and estimate the size of the period. Suppose we can prove that for D(f6)(n), the eventual period has to start before n reaches A, and the length of the eventual period is not more than B. Then, we need to calculate the A + 2B values of the function f6(n) to know the function for any n.
Derek actually calculated the functions fm(n) and gm(n) for m up to 9 and n up to infinity. More precisely, he found the cycles I am describing above. What a mindblowing achievement!
[…] However, you have access to a computer, and some coding skills! So, we will give you a harder version of this problem on a rectangular m × n chessboard with an additional constraint: the knight may never cross its own path. If you imagine its path consisting of straight line segments connecting the centers of squares it jumps between, these segments must form a simple polygon; that is, no two segments intersect or touch, except that consecutive segments touch at their common end point. This constraint makes it impossible to visit every square, so instead you must maximize the number of squares the knight visits. We keep the constraint that the knight must return to its starting square. Figure J.1 shows an optimal solution for the first sample input, a 6 × 6 board. … (Tanya Kovanova) […]
Thanks for the shout-out! This was a neat problem to look at, particularly because it makes some pretty pictures. 🙂
Regarding the “mathematical theory”, I find it’s easiest to rephrase the problem as a graph problem. For a given M, we have a finite graph (representing all DP states) with weighted directed edges, and a Start/End node. The problem bcomes “what is the highest sum of weights for a path of length N from Start to End”; the challenge is to prove that this will eventually be periodic, since all paths will eventually be dominated by the highest-ratio cycle (the “densest pattern”). Technically, for the proof, you also need the condition that the graph doesn’t end up periodically oscillating between multiple different behaviors (similar to how a Markov Chain usually converges to a stable distribution unless it oscillates), but in this case the edge End -> End exists, which makes that impossible.
To compute results in practice, it’s not too useful to compute a theoretical limit to the period, because that can be very high – I think it’s potentially (max edge weight) * (num of nodes)^2 if you have a 2nd-best-ratio cycle that is only dominated by the highest-ratio cycle after a long time. Instead, my search program can just observe when the cycle starts, because all the states of the DP have values that are just a constant added to all the states of the DP X turns ago. For a problem like this, the cycle (fortunately) occurs much faster than the theoretical limit.
I’m an avid chess player, and I enjoyed reading this article. I also only know a small amount about dynamic programming, but I heard a number of talks about this topic when I was a graduate student. It was also interesting to learn more about the knight tours on the non-standard chess boards, such as those that are 6 x 24 or 6 x 26.
Do the difficult chess knight dance – The nth Root:
[…] However, you have access to a computer, and some coding skills! So, we will give you a harder version of this problem on a rectangular m × n chessboard with an additional constraint: the knight may never cross its own path. If you imagine its path consisting of straight line segments connecting the centers of squares it jumps between, these segments must form a simple polygon; that is, no two segments intersect or touch, except that consecutive segments touch at their common end point. This constraint makes it impossible to visit every square, so instead you must maximize the number of squares the knight visits. We keep the constraint that the knight must return to its starting square. Figure J.1 shows an optimal solution for the first sample input, a 6 × 6 board. … (Tanya Kovanova) […]
20 December 2022, 3:57 pmDerek Kisman:
Thanks for the shout-out! This was a neat problem to look at, particularly because it makes some pretty pictures. 🙂
Regarding the “mathematical theory”, I find it’s easiest to rephrase the problem as a graph problem. For a given M, we have a finite graph (representing all DP states) with weighted directed edges, and a Start/End node. The problem bcomes “what is the highest sum of weights for a path of length N from Start to End”; the challenge is to prove that this will eventually be periodic, since all paths will eventually be dominated by the highest-ratio cycle (the “densest pattern”). Technically, for the proof, you also need the condition that the graph doesn’t end up periodically oscillating between multiple different behaviors (similar to how a Markov Chain usually converges to a stable distribution unless it oscillates), but in this case the edge End -> End exists, which makes that impossible.
To compute results in practice, it’s not too useful to compute a theoretical limit to the period, because that can be very high – I think it’s potentially (max edge weight) * (num of nodes)^2 if you have a 2nd-best-ratio cycle that is only dominated by the highest-ratio cycle after a long time. Instead, my search program can just observe when the cycle starts, because all the states of the DP have values that are just a constant added to all the states of the DP X turns ago. For a problem like this, the cycle (fortunately) occurs much faster than the theoretical limit.
20 December 2022, 5:53 pmtanyakh:
Thank you, Derek, for the explanation.
I am surprised I understood it.
20 December 2022, 6:00 pmAndrew:
I’m an avid chess player, and I enjoyed reading this article. I also only know a small amount about dynamic programming, but I heard a number of talks about this topic when I was a graduate student. It was also interesting to learn more about the knight tours on the non-standard chess boards, such as those that are 6 x 24 or 6 x 26.
Andrew
Founder of MathTutorPro.com
29 January 2023, 11:46 am