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.

M	T	W	T	F	S	S
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30

Yet Another Mathblog