# Odd king tours on even chessboards

This blog post discusses a paper “Odd king tours …” written with Michael Fourte (a CS undergrad at the time, now is a lawyer and Naval officer in NYC) in 1997. It was published in the now defunct Journal of Recreational Mathematics, issue 31(3), in 2003.

In the paper, we showed that there is no complete odd king tour on an even chessboard, partially answering a question raised in [BK], [S]. This post surveys that paper. King moves on an 8×8 board.

A complete king tour on an $m\times n$ board may be represented graph theoretically as a Hamiltonian cycle on a particular graph with $mn$ vertices, of which $(m-2)\cdot (n-2)$ of them have degree $8$, $2(m+n-4)$ have degree $5$ and the remaining $4$ vertices have degree $3$. The problem of finding an algorithm to find a hamiltonian circuit in a general graph is known to be NP complete. The problem of finding an efficient algorithm to search for such a tour therefore appears to be very hard problem. In [BK], C. Bailey and M. Kidwell proved that complete even king tours do not exist. They left the question of the existence of complete odd tours open but showed that if they did exist then it would have to end at the edge of the board.

We shall show that
Theorem: No complete odd king tours exist on an $m\times n$ board, except possibly in the following cases:

• $m=n=7$
• $m=7$ and $n=8$,
• $m >7$, $n >7$ and $m$ or $n$ (or both) is odd,
• $m>7$, $n>7$ and the tour is “rapidly filling”.

The definition of “rapidly filling” requires some technical notation and will be given later.

### Background

Before proving this, we recall briefly some definitions and results from [BK] which we shall use in our proof.

Definition: Two squares are called a neighbor pair if they have a common edge or common vertex. A neighbor pair is called completed if both squares have been visited by the the king at some point in a tour, including the case where the king is still on one of the squares. A foursome is a collection of four squares which form a $2\times 2$ array of neighboring squares on the board. A foursome is called completed if all four squares have been visited by the the king at some point in a tour, including the case where the king is still on one of the four squares.

Unless stated otherwise, after a given move of a given odd king tour, let $\Delta F$ denote the change in the number of completed foursomes and let $\Delta N$ denote the change in the number of completed neighbor pairs. Note that $\Delta N$ is equal to the total number of previously visited squares which are neighboring the king.

The following result was proven in [BK] using a counting argument.

Lemma:

• The number of neighbor pairs of an $m\times n$ board is $2mn+2(m-1)(n-1)-m-n.$
• (b) The number of foursomes of an $m\times n$ board is $(m-1)(n-1).$

The following result was proven in [BK] using a case-by-case argument:

Lemma: After a particular move in a given even king tour, let $\Delta F$ denote the change in the number of completed foursomes and let $\Delta N$ denote the change in the number of completed neighbor pairs. If $\Delta F=0$ then $\Delta N\geq 2$. If $\Delta F=1$ then $\Delta N\geq 4$. If $\Delta F=2$ then $\Delta N\geq 6$. If $\Delta F=3$ then $\Delta N =8$.

We shall need the proof of this lemma (for which we refer the reader to [BK]) rather than the lemma itself. The proof of this lemma implies the following:

Lemma: For an odd king tour: If $\Delta F=0$ then $Delta N\geq 1$. If $\Delta F=1$ then $\Delta N \geq 3$. If $\Delta F=2$ then $\Delta N\geq 5$. If $\Delta F=3$ then $\Delta N =7$.

The proof is omitted.

Definition: We call an odd king tour rapidly filling if there is a move in the tour such that $2\Delta F +1<\Delta N$ and $1\leq \Delta F$.

### The proof of the theorem

Proposition: If $m$ and $n$ are both even then no complete odd king tour exists.

proof: Let $N$ denote the total number of completed neighbor pairs after a given point of a given odd king tour. We may represent the values of $N$ as a sequence of numbers, $0,1,2,...$. Here $0$ is the total number of completed neighbor pairs after the first move, $1$ for after the second move, and so on. Each time the king moves, $N$ must increase by an odd number of neighbors – either $1$, $3$, $5$, or $7$. In particular, the parity of $N$ alternates between odd and even after every move. If $m$ and $n$ are both even and if a complete odd king tour exists then the the final parity of $N$ must be odd. By the lemma above, the value of $N$ after any complete king tour is $2mn+2(m-1)(n-1)-m-n$, which is obviously even. This is a contradiction. QED

It therefore suffices to prove the above theorem in the case where at least one of $m,n$ is odd. This follows from a computer computation, an argument from Sands [Sa], and the sequence of lemmas that follow. The proofs are in the original paper, and omitted.

Let $N$ denote the total number of completed neighbor pairs in a given odd king tour. Let $F$ denote the number of completed foursomes in a given odd king tour. Let $M$ denote the number of moves in a given odd king tour. Let $T=N-2M-2F+4.$

Lemma: Let $\Delta T=\Delta N - 2 - 2\Delta F$, where $\Delta N ,\Delta F$ are defined as above. Then $\Delta T$ equals $-1$, $1$, $3$, or $5$. If the tour is not rapidly filling then $\Delta T\geq 1$ only occurs when $\Delta F= 0$.

Lemma: Let $H(m,n)$ denote the largest number of non-overlapping $2\times 2$ blocks which will fit in the $m\times n$ board. There are no labelings of the $m\times n$ checkerboard by $0$‘s and $1$‘s with no $2\times 2$ blocks of $1$‘s and fewer than $H(m,n)$ $0$‘s. In particular, if there are no $2\times 2$ blocks of 1’s then there must be at least $[m/2][n/2]$ 0’s.

We conclude with a question. An odd king tour of length $mn-1$ on an $m\times n$ board will be called nearly complete. Which boards have nearly complete odd king tours? We conjecture: If $n >$ then all $7\times n$ boards have nearly complete odd king tours.

### References

[BK] C. Bailey, M. Kidwell, “A king’s tour of the chessboard”, Math. Mag. 58(1985)285-286

[S] S. Sacks, “odd and even”, Games 6(1982)53.

[Sa] B. Sands, “The gunport problem”, Math. Mag. 44(1971)193-194.

# Mathematicians and Chess

• which mathematicians (which we define as someone who has earned a PhD or equivalent in Mathematics) play(ed) chess at the International Master level or above (in OTB or correspondence or problem composing), and
• how to get papers on mathematical chess problems.

Similar pages are here and here and here and here.

## Mathematicians who play(ed) chess

• Conel Hugh O’Donel Alexander (1909-1974), late British chess champion. Alexander may not have had a PhD in mathematics but taught mathematics and he did mathematical work during WWII (code and cryptography), as did the famous Soviet chess player David Bronstein (see the book Kahn, Kahn on codes). He was the strongest English player after WWII, until Jonathan Penrose appeared.
• Adolf Anderssen (1818-1879). Pre World Championships but is regarded as the strongest player in the world between 1859 and 1866. He received a degree (probably not a PhD) in mathematics from Breslau University and taught mathematics at the Friedrichs gymnasium from 1847 to 1879. He was promoted to Professor in 1865 and was given an honorary doctorate by Breslau (for his accomplishments in chess) in 1865.
• Magdy Amin Assem (195?-1996) specialized in p-adic representation theory and harmonic analysis on p-adic reductive groups. He published several important papers before a ruptured aneurysm tragically took his life. He was IM strength (rated 2379) in 1996.
• Gedeon Barcza (1911-1986), pronounced bartsa, was a Hungarian professor of mathematics and a chess grandmaster. The opening 1.Nf3 d5 2.g3 is called the Barcza System. The opening 1.e4 e6 2.d4 c5 is known as the Barcza-Larsen Defense.
• Ludwig Erdmann Bledow (1795-1846) was a German professor of mathematics (PhD). He founded the first German chess association, Berliner Schachgesellschaft, in 1827. He was the first person to suggest an international chess tournament (in a letter to von der Lasa in 1843). His chess rating is not known but he did at one point win a match against Adolf Anderssen.
• Robert Coveyou (1915 – 1996) completed an M.S. degree in Mathematics, and joined the Oak Ridge National Laboratory as a research mathematician. He became a recognized expert in pseudo-random number generators. He is known for the quotation “The generation of random numbers is too important to be left to chance,” which is based on a title of a paper he wrote. An excellent tournament chess player, he was Tennessee State Champion eight times.
• Nathan Divinsky (1925-2012) earned a PhD in Mathematics in 1950 from the University of Chicago and was a mathematics professor at the University of British Columbia in Vancouver. He tied for first place in the 1959 Manitoba Open.
• Noam Elkies (1966-), a Professor of Mathematics at Harvard University specializing in number theory, is a study composer and problem solver (ex-world champion). Prof. Elkies, at age 26, became the youngest scholar ever to have attained a tenured professorship at Harvard. One of his endgame studies is mentioned, for example, in the book Technique for the tournament player, by GM Yusupov and IM Dvoretsky, Henry Holt, 1995. He wrote 11 very interesting columns on Endgame Exporations (posted by permission).
Some other retrograde chess constructions of his may be found at the interesting Dead Reckoning web site of Andrew Buchanan.
• Thomas Ernst earned a Ph.D. in mathematics from Uppsala Univ. in 2002 and does research in algebraic combinatorics with applications to mathematical physics. His chess rating is about 2400 (FIDE).
• Machgielis (Max) Euwe (1901-1981), World Chess Champion from 1935-1937, President of FIDE (Fédération Internationale des Echecs) from 1970 to 1978, and arbitrator over the turbulent Fischer – Spassky World Championship match in Reykjavik, Iceland in 1972. I don’t know as many details of his mathematical career as I’d like. One source gives: PhD (or actually its Dutch equivalent) in Mathematics from Amsterdam University in 1926. Another gives: Doctorate in philosophy in 1923 and taught as a career. Published an important paper on the mathematics of chess “Mengentheoretische Betrachtungen uber das Schachspiel”. This paper lead to a rule change in chess regarding the 3-times repetition draw. • Ed Formanek (194?-), International Master. Ph.D. Rice University 1970. Retired from the mathematics faculty at Penn State Univ. Worked primarily in matrix theory and representation theory.
• Stephen L. Jones is an attorney in LA, but when younger, taught math in the UMass system and spent a term as a member of the Institute for Advanced Study in Princeton NJ. He is one rung below the level of International Master at over the board chess; in correspondence chess, he has earned two of the three norms needed to become a Grandmaster.
• Charles Kalme (1939-2002), earned his master title in chess at 15, was US Junior champ in 1954, 1955, US Intercollegiate champ in 1957, and drew in his game against Bobby Fischer in the 1960 US championship. In 1960, he also was selected to be on the First Team All-Ivy Men’s Soccer team, as well as the US Student Olympiad chess team. (Incidently, it is reported that this team, which included William Lombary on board one, did so well against the Soviets in their match that Boris Spassky, board one on the Soviet team, was denied forieng travel for two years as punishment.) In 1961 graduated 1st in his class at the Moore School of Electrical Engineering, The University of Pennsylvania, in Philadelphia. He also received the Cane award (a leadership award) that year. After getting his PhD from NYU (advisor Lipman Bers) in 1967 he to UC Berkeley for 2 years then to USC for 4-5 years. He published 2 papers in mathematics in this period, “A note on the connectivity of components of Kleinian groups”, Trans. Amer. Math. Soc. 137 1969 301–307, and “Remarks on a paper by Lipman Bers”, Ann. of Math. (2) 91 1970 601–606. He also translated Siegel and Moser, Lectures on celestial mechanics, Springer-Verlag, New York, 1971, from the German original. He was important in the early stages of computer chess programming. In fact, his picture and annotations of a game were featured in the article “An advice-taking chess computer” which appeared in the June 1973 issue of Scientific American. He was an associate editor at Math Reviews from 1975-1977 and then worked in the computer industry. Later in his life he worked on trying to bring computers to elementary schools in his native Latvia A National Strategy for Bringing Computer Literacy to Latvian Schools. His highest chess rating was acheived later in his life during a “chess comeback”: 2458.
Here is his game against Bobby Fischer referred to above:[Event “?”]
[Site “New York ch-US”]
[Date “1960.??.??”]
[Round “3”]
[White “Fischer, Robert J”]
[Black “Kalme, Charles”]
[Result “1/2-1/2”]
[NIC “”]
[Eco “C92”]
[Opening “Ruy Lopez, Closed, Ragozin-Petrosian (Keres) Variation”]
1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Ba4 Nf6 5.O-O Be7 6.Re1 b5 7.Bb3 O-O 8.c3 d6 9.h3 Nd7 10.a4 Nc5 11.Bd5 Bb7 12.axb5 axb5 13.Rxa8 Qxa8 14.d4 Nd7 15.Na3 b4 16.Nc4 exd4 17.cxd4 Nf6 18.Bg5 Qd8 19.Qa4 Qa8 20.Qxa8 Rxa8 21.Bxf6 Bxf6 22.e5 dxe5 23.Ncxe5 Nxe5 24.Bxb7 Nd3 25.Bxa8 Nxe1 26.Be4 b3 27.Nd2 1/2-1/2
• Miroslav Katetov (1918 -1995) earned his PhD from Charles Univ in 1939. Katetov was IM chess player (earned in 1951) and published about 70 research papers, mostly from topology and functional analysis.
• Martin Kreuzer (1962-), CC Grandmaster, is rated over 2600 in correspondence chess (ICCF, as of Jan 2000). His OTB rating is over 2300. His specialty is computational commutative algebra and applications. Here is a recent game of his:
Kreuzer, M – Stickler, A
[Eco “B42”]
[Opening “Sicilian, Kan”]
1.e4 c5 2.Nf3 e6 3.d4 cxd4 4.Nxd4 a6 5.Bd3 Nc6 6.c3 Nge7 7.0-0 Ng6 8.Be3 Qc7 9.Nxc6 bxc6 10.f4 Be7 11.Qe2 0-0 12.Nd2 d5 13.g3 c5 14.Nf3 Bb7 15.exd5 exd5 16.Rae1 Rfe8 17.f5 Nf8 18.Qf2 Nd7 19.g4 f6 20.g5 fxg5 21.Nxg5 Bf6 22.Bf4 Qc6 23.Re6 Rxe6 24.fxe6 Bxg5 25.Bxg5 d4 26.Qf7+ Kh8 27.Rf3 Qd5 28.exd7 Qxg5+ 29.Rg3 Qe5 30.d8=Q+ Rxd8 31.Qxb7 Rf8 32.Qe4 Qh5 33.Qe2 Qh6 34.cxd4 cxd4 35.Bxa6 Qc1+ 36.Kg2 Qc6+ 37.Rf3 Re8 38.Qf1 Re3 39.Be2 h6 40.Kf2 Re8 41.Bd3 Qd6 42.Kg1 Kg8 43.a3 Qe7 44.b4 Ra8 45.Qc1 Qd7 46.Qf4 1-0
• Emanuel Lasker (1868-1941), World Chess Champion from 1894-1921, PhD (or more precisely its German equivalent) in Mathematics from Erlangen Univ in 1902. Author of the influential paper “Zur theorie der moduln und ideale,” Math. Ann. 60(1905)20-116, where the well-known Lasker-Noether Primary Ideal Decomposition Theorem in Commutative Algebra was proven (it can be downloaded for free here). Lasker wrote and published numerous books and papers on mathematics, chess (and other games), and philosophy.
• Vania Mascioni, former IECG Chairperson (IECG is the Internet Email Chess Group), is rated 2326 by IECG (as of 4-99). His area is Functional Analysis and Operator Theory.
• A. Jonathan Mestel, grandmaster in over-the-board play and in chess problem solving, is an applied mathematician specializing in fluid mechanics and is the author of numerous research papers. He is on the mathematics faculty of the Imperial College in London.
• Walter D. Morris (196?-), International Master. Currently on the mathematics faculty at George Mason Univ in Virginia.
• Karsten Müller earned the Grandmaster title in 1998 and a PhD in mathematics in 2002 at the University of Hamburg.
• John Nunn (1955-), Chess Grandmaster, D. Phil. (from Oxford Univ.) in 1978 at the age of 23. His PhD thesis is in algebraic topology. Nunn is also a GM chess problem solver.
• Hans-Peter Rehm (1942-), earned his PhD in Mathematics from Karlsruhe Univ. (1970) then taught there for many years. He is a grandmaster of chess composition. He has written several papers in mathematics, such as “Prime factorization of integral Cayley octaves”, Ann. Fac. Sci. Toulouse Math (1993), but most in differential algebra, his specialty. A collection of his problems has been published as: Hans+Peter+Rehm=Schach Ausgewählte Schachkompositionen & Aufsätze (= selected chess problems and articles), Aachen 1994.
• Kenneth W. Regan, Professor of Computer Science at the State Univ. of New York Buffalo, is currently rated 2453. His research is in computational complexity, a field of computer science which has a significant mathematical component.
• Jakob Rosanes obtained his mathematics doctorate from the Univ. of Breslau in 1865 where he taught for the rest of his life. In the 1860s he played a match against A. Anderssen which ended with 3 wins, 3 losses, and 1 draw.
• Jan Rusinek (1950-) obtained his mathematics PhD in 1978 and earned a Grandmaster of Chess Composition in 1992.
• Jon Speelman (1956-) is an English Grandmaster chess player and chess writer. He earned his PhD in mathematics from Oxford.

Others that might go on this list would be Henry Ernest Atkins (he taught mathematics but never got a PhD, but won the British Chess Championship 9 times in the early 1900s), Andrew Kalotay (who earned a PhD in statistics in 1968 from the Univ of Toronto, and was a Master level chess player but was not formally given an IM chess ranking), Kenneth Rogoff (has a PhD in economics but has published statistics research papers and is a GM in chess), and Duncan Suttles (in the 1960s he started but never finished his PhD in mathematics, but is a chess GM).

## Papers about mathematical problems in chess

Thanks to Christoph Bandelow, Max Burkett, Elaine Griffith, Hannu Lehto, John Kalme, Ewart Shaw, Richard Stanley, Will Traves, Steven Dowd, Z. Kornin, Noam Elkies and Hal Bogner for help and corrections on this page. This page is an updated version of that page and the other page.