June Huh, Combinatorics, and the Strange Allure of Chess Knight Problems

Andrei Mihai

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.

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.

The post June Huh, Combinatorics, and the Strange Allure of Chess Knight Problems originally appeared on the HLFF SciLogs blog.