June Huh, Combinatorics, and the Strange Allure of Chess Knight Problems
BLOG: Heidelberg Laureate Forum
June Huh was awarded the Fields Medal in 2022 for his transformative contributions to the field of combinatorics, particularly for the bridges he built between combinatorics and algebraic geometry. However, his story is not at all linear and straightforward – and it intertwines with poetry, science, and a particular type of chess problems.
The Poetry of Mathematics
In high school, Huh wanted to be a poet. He even dropped out of high school to focus on his poetry, feeling exhausted by the relentless studying. His poetry did not do all that well.
His university studies were also fraught with difficulties. He wanted to major in physics and astronomy and become a science journalist. However, his attendance record was poor and he had to repeat several courses after failing them.
If there was anything Huh knew he didn’t want to do, it was mathematics. “I was pretty good at most subjects except math,” he told the New York Times. However, there were glimpses of Huh’s mathematical brilliancy, it just did not seem like math.
Huh recalls one such flash coming from the unlikeliest of settings: a computer horror game. The 11th Hour, a 1995 computer game, had the player investigate a series of grisly events and piece things together. The player is tasked with solving various problems, some of which were notably complex.
Among them, one puzzle haunted Huh. It was a chess puzzle.
The puzzle seems simple enough. It is only a few squares and you only have four knights (the knights move in an “L” shape, like in regular chess). The goal is also straightforward: swap the positions of the black and white knights.
At first glance, the task seems trivial. You just move the knights around until something works. But it is not that simple – try it out.
It took the young Huh a week to solve, but for him, it was not just about solving the problem. It was about understanding what the problem actually meant.
In a mathematical sense, the way the knights move does not matter. The shape and size of the board also does not matter. What matters is the geometry of the blocks and the relationships between them. Essentially, the chess puzzle can be reinterpreted as a graph. Each knight can move to an unoccupied space on this graph, and this makes solving the problem much easier.
The first step is establishing a notation.
With this notation, instead of visualizing the knight moves geometrically, you can see them as a graph of possible moves from one space to another.
The knight can move from “1” to “5” and nowhere else. From “5,” it can go back to “1” or to “7.” In fact, the only box that has three places the knight can go is “2.” Herein lies the key.
When we add the knights, the problem takes this form:
With the above image, it becomes much more apparent what the way forward is. We have the “9” square that we can use as a hideaway for one knight, while we maneuver the other three. If we want to swap the white and black knights, we simply need to tuck the black ones away one at a time and move the white ones to their left (as shown on this graph). Try it!
Translating to Mathematics
This approach of visualizing problems in a mathematical fashion, fascinated Huh and drew him to mathematics. This particular type of problem is called a chromatic polynomial.
Imagine you have a map or a network of nodes connected by edges, like cities connected by roads or regions on a map bordered by boundaries. The chromatic polynomial of this network (or graph) tells you the number of ways you can color the nodes (or regions) with a given number of colors, such that no two adjacent nodes (or neighboring regions) share the same color.
This idea is not just about chess. It has practical applications in logistics and optimization problems, statistical physics (particularly in the study of phase transitions), and network analysis.
Translating problems into mathematical expressions became more than just a hobby for Huh. In his last year of college, Huh started to really fall in love with math. He attended a course by Heisuke Hironaka, a Japanese mathematician who had won a Fields Medal in 1970. Huh would become Hironaka’s Master’s student and received a letter of recommendation. It was a strange combination: a student who had failed several mathematics courses but had an enthusiastic recommendation from a leading mathematician. It was almost not enough. All but one of the universities that Huh applied to rejected him. The University of Illinois Urbana-Champaign put him on a waiting list and then, ultimately, accepted him.
Thus began the research journey of June Huh. Following a reluctant path into mathematics, he would go on to revolutionize the field of combinatorics, reinvigorating the field and intertwining it with some of the most esoteric areas of geometry.
However, Huh is far from the only mathematician drawn to chess knight puzzles.
The Infamous Knight Tour
Perhaps the most famous knight problem is the so-called “knight’s tour.” The premise is, once again, very simple. You have a square chessboard of a given dimension and one knight. You have to move the knight in a way that covers all the squares, without going to the same square twice. Something like this:
The problem can be applied to a number of different board sizes.
This too can be generalized as a Hamiltonian path problem in graph theory. But unlike Huh’s problem, this one dates from much earlier.
The earliest known reference to a knight’s tour problem dates back to the 9th century, from a Sanskrit work. Kashmiri poet and literary theorist Rudrata presented the knight’s tour as a verse in four lines of eight syllables each – another surprising mixing of poetry and mathematics.
Famous mathematician Leonhard Euler also looked at the problem, but it was H. C. von Warnsdorf who developed the first traceable algorithm to solve the knight’s tour. Warnsdorf postulated the following rule: “Move the knight to a square from which it will have the fewest available subsequent moves.”
This simple rule is surprisingly effective, but it is not perfect. It produces valid tours in the vast majority of cases on boards smaller than 50×50, but not all the time.
As it turns out, finding a workable, generalizable algorithm for knight’s tours is more difficult than it may appear. This comes from the sheer complexity of larger boards. For instance, the smallest board for which a knight’s tour yields solutions is 5×5. For a board of that size, there are over 1,700 possible tours (tours are considered different if they start from different places or have different trajectories; they can be mirrored or rotated).
That number quickly gets much, much larger.
| n | Number of directed tours (open and closed) on an n × n board |
| 1 | 1 |
| 2 | 0 |
| 3 | 0 |
| 4 | 0 |
| 5 | 1,728 |
| 6 | 6,637,920 |
| 7 | 165,575,218,320 |
| 8 | 19,591,828,170,979,904 |
Remarkably, the problem even lends itself to a neural network algorithm. This was first discussed in 1992 in a paper spearheaded by Yoshiyasu Takefuji from Keio University in Japan, with a network set up so that each move is essentially a neuron in the network.
The allure of such knight problems and the surprising richness and depth that emerge from them says something about mathematics in itself. There is a generalizable trait of mathematics that is often ignored: the inherent beauty in its patterns and solutions.
For June Huh, this realization came from a place of artistic pursuit and a seemingly unrelated game puzzle, illustrating how the paths to mathematical success are as varied as the individuals who walk them.
Andrei Mihai wrote (01. May 2024):
> […] a chess puzzle. [ https://scilogs.spektrum.de/hlf/files/problema-chessyy_2.png ] Image created by the author [ AM ].
> The puzzle seems simple enough. It is only a few squares and you only have four knights (the knights move in an “L” shape, like in regular chess). The goal is also straightforward: swap the positions of the black and white knights.
> At first glance, the task seems trivial. You just move the knights around until something works. But it is not that simple – try it out.
It’s not simple, indeed — presuming that all usual chess rules of apply, as far as they can be construed as applying to this very specific problem; namely, aside of each knight’s move having to be “L” shape as pointed out above:
(a) each move must take exactly one knight, from its field of origin to another applicable one of the fields of the (partial) board shown in the above image;
(b) at the end of any one move, knights of the same color must stand on distinct fields of the board;
(c) at the end of any one move, all four knights must stand on distinct fields of the board.
(The otherwise regular possibility of moving a chess piece to take (capture) one piece of the opposite color cannot apply in this particular problem because two white knights and two black knights are required to be present in the goal position, too, but there are no pawns given initially for any regular conversion, etc.);
and last but not least:
(d) after a knight of one color has moved, a knight of the opposite color must move, and so on, alternatingly; unless the goal position has been reached.
These listed rules together enforce that white must be first to move; and indeed that the first three (half-)moves must be as follows:
1. wN72 bN57
2. wN26 …
(adapted to the notation introduced and used in the subsequent figures of the SciLog article)
.
> […] what the way forward is. We have the “9” square that we can use as a hideaway for one knight, while we maneuver the other three. If we want to swap the white and black knights, we simply need to tuck the black ones away one at a time and move the white ones to their left (as shown on this graph). […]
As shown on which graph exactly, please ?
(Sorry — I don’t mean to insist on being given the solution outright, but:
having tried a reasonable while to solve the puzzle by strictly following the “chess rules” (a) – (d) as spelt out above, since I considered them applicable … now I’m beginning to wonder whether there is a solution to the proposed “chess puzzle” under these exact conditions at all.
Specificly, how to avoid White from being — so to say — smothered, i.e. being unable to carry out a move although it’s white’s turn to move, on the way to attempting the “tuck-away-maneuvre” on the second black knight.
For example: Consider the “not too far fetched” intermediate position
“wN1, bN5, wN7, bN9”
which apparently would have been reached by the white half-move “wN27” (how else ?? …).
Therefore it’s Black’s turn, with the only available half-move “… bN92”.
Then: What ?? — Game over.)
Or: Are these supposed “chess rules” (a) – (d) not to be considered in effect, for solving the puzzle ??
Andrei Mihai wrote (01. May 2024):
> […] a chess puzzle. [ https://scilogs.spektrum.de/hlf/files/problema-chessyy_2.png ] Image created by the author [ AM ].
> The puzzle seems simple enough. It is only a few squares and you only have four knights (the knights move in an “L” shape, like in regular chess). The goal is also straightforward: swap the positions of the black and white knights.
> At first glance, the task seems trivial. You just move the knights around until something works. But it is not that simple – try it out.
It’s not simple, indeed — presuming that all usual chess rules are in effect, as far as they can be construed as applying to this very specific problem. Namely, aside of each knight’s move having to be “L” shaped as pointed out above:
(a) each move must take exactly one knight, from its field of origin to another applicable one of the fields of the (partial) board shown in the above image;
(b) at the end of any one move, knights of the same color must stand on distinct fields of the board;
(c) at the end of any one move, all four knights must stand on distinct fields of the board.
(The otherwise basic possibility of »moving a chess piece to take (capture) one piece of the opposite color« cannot apply in this particular problem because two white knights and two black knights are required to be present in the goal position, too, but there are no pawns given initially for any regular conversion, etc.);
and last but not least:
(d) after a knight of one color has moved, a knight of the opposite color must move, and so on, alternatingly; unless the goal position has been reached.
These listed rules together enforce that white must be first to move; and indeed that the first three (half-)moves must be as follows:
1. wN72 bN57
2. wN26 …
(adapted to the notation introduced and used in the subsequent figures of the SciLog article)
.
> […] what the way forward is. We have the “9” square that we can use as a hideaway for one knight, while we maneuver the other three. If we want to swap the white and black knights, we simply need to tuck the black ones away one at a time and move the white ones to their left (as shown on this graph). […]
As shown on which graph exactly, please ?
(Sorry — I don’t mean to insist on being given the solution outright, but:
having tried a reasonable while to solve the puzzle by strictly following the “chess rules” (a) – (d) as spelt out above, since I considered them applicable … now I’m beginning to wonder whether there is a solution to the proposed “chess puzzle” under these exact conditions at all.
Specificly, how to avoid White from being — so to say — »smothered«, i.e. being unable to carry out any move at all although it’s white’s turn to move, on the way to attempting the “tuck-away-maneuvre” on the second black knight.
For example: Consider the “not too far fetched” intermediate position
“wN1, bN5, wN7, bN9”
which apparently would have been reached by the white half-move “wN27” (how else ?? …).
Therefore it’s Black’s turn, with the only available half-move “… bN92”.
Then: What ?? — Game over.)
Or: Are these supposed “chess rules” (a) – (d) not to be considered in effect, for solving the puzzle ??
ps:
An as good as equivalent puzzle has been assigned as »Question 11« in sect. 2, p. 8, of the »Mathematics Olympiad 2023« of the Mathematics Association II Bombay.
There is explicitly asked
ps:
An as good as equivalent puzzle has been assigned as »Question 11« in sect. 2, p. 8, of the »Mathematics Olympiad 2023« of the Mathematics Association IIT Bombay.
There is explicitly asked
Arguably (as far as I understand) this quoted prescription does not insist that a move by one piece of one color must be followed by a move of a piece of the other color, alternatingly, until the puzzle is solved (just as chess moves are done alternatingly until the game has finished; with the “castling” move constituting an exceptional case).
My question therefore remains whether the puzzle can be solved by legal moves taking alternating turns with pieces of opposite colors, as we naturally do in playing chess.
It was my initial understanding that the “legal” move part also refers to knight moving “as a knight” and not to black and white moving alternatively. However, if you want to do it like this, you can avoid getting smothered if I’m not mistaken.
From the starting position (this is the easiest visualization: https://scilogs.spektrum.de/hlf/files/problemachessyxx-2048×484.png) simply move the white (7) and black (5) knights to the right. But not all the way — only to 3 and 10. Then, the white knight can oscilate between 10 and 4 while the second black knight (starting in 1) can make its way to 6.
Essentially, you save little pockets of movement and move back and forth with one color while you maneuver with the other.
Andrei Mihai wrote (15.05.2024, 23:37 o’clock):
> It was my initial understanding that the “legal” move part also refers to knight moving “as a knight” and not to black and white moving alternatively.
Thanks for your reply. As I got around researching only this morning:
The NYT article mentions the source of the specific puzzle that occupied June Huh, and the corresponding “official” »Solution in 40 moves« (which is kindly provided, too) readily matches your understanding — there was no requirement of black and white moving alternatingly in this original version of the puzzle.
> However, if you want to do it like this,
… yes — at least I’d like to explore and settle the question whether there is any solution at all with knights of either color each taking only one move in turn (as chess pieces do in regular games and chess problems) …
> you can avoid getting smothered if I’m not mistaken. […]
Oh, but I’m (at the moment) under the impression that you are mistaken about that! — Please compare (again) with the example from my first comment (13.05.2024, 18:38 o’clock), which deals with (one of only few variants of) “the (most) critical stage”. …
Essentially and (to my present understanding) decisively:
The »oscillation maneuvers« involving three knights, as you described in your comment, which can easily be realized on the five fields “6”, “8”, “3”, “10” and “4” (in the notation of your SciLogs article above) that are consecutive to one side of “fork field” “2”, seem impossible on the (only) three consecutive fields (“7”, “5” and “1”) to the other side of the “fork field” “2”.
Yes on second thought I think in this scenario where you must take alternate movements, you’re right. There’s one critical point after you swap one of the black knights after which you get smothered.