Investigating closed knight's tours in 3 × 2k chess boards

I play chess at a competitive level, and I have always felt that chess hassome Mathematics hidden in it because of all the possible combinations and permutations of positions it offers and because of its strictly logical nature, mimicking that of Mathematics. I discovered the knight’s tour puzzle some years ago and was immediately fascinated by it, given also that my favourite piece in chess is the knight due to its particular movement, which sets it apart from the other pieces. However, I had never explored the knight’s tour in great depth, and now this is my chance to delve further into this puzzle, understand it, and extend my knowledge by exploring more complex variations, applying the Mathematics of graph theory. My aim is to understand the dimensions of irregular chessboards for which there are Knight’s tours, prove this, and then go on to investigate a relationship involving the number of tours in a particular scenario.

This exploration focuses specifically on determining how many closed knight tours are possible in irregular chessboards, by first determining and proving for which dimensions of the chessboards this is actually possible. Chess is a two-player game which is generally played on a square board with 8 rows and 8 columns. However, for the purposes of this investigation, chessboards with j rows and k columns will be considered, where k ≠ 8, j ≤ k and j = 3. j = 3 and k ≠ 8 were chosen because they provide the ideal combination of a project which can be explored deeply without resorting to extremely complicated mathematics, which could hinder communication, and at the same time these dimensions give me the ability to conduct a major personal investigation, given that boards with k = 8 have been thoroughly investigated by many academics and I would be merely replicating their ideas, while there has been significantly less research into boards with k ≠ 8. If we assume that the orientation of the chessboard is fixed, it is possible to label all the squares. For this exploration, every square on the chessboard will be denoted by the ordered pair (x, y), where x is the row number and y is the column number.

The knight is one of the pieces used in chess; it moves as shown in the diagram aside -

Without loss of generality, in this exploration the Knight will start its tour from the top left corner in the chess board.

In this investigation, two squares will be defined as being adjacent if the knight can, with one move, go from one to the other. This is not a chess term, but rather a term chosen solely for this investigation.

Let the square the knight moves from be denoted by (x, y); then, starting at square (x, y), a knight can move to one of the following squares: (x ± 2, y ± 1) or (x ± 1, y ± 2). Whether the knight can go to all of these squares depends on where it starts on the chessboard, since some of the squares may be outside of the actual chessboard.

In this exploration, the individual squares (x, y) on the chessboard will be referred to using matrix notation, counting from the top left corner, as the following example for a 3 × 3 board shows -

\(\begin{bmatrix} 1,1 & 1,2 & 1,3 \\ 2,1 & 2,2 & 2,3 \\ 3,1 & 3,2 & 3,3 \end{bmatrix}\)

A knight’s tour is thus defined as a sequence of squares, where all pairs of consecutive squares are adjacent and unique. A square is named ‘visited’ if it has already been occupied by the knight, otherwise it is named ‘unvisited’.

This investigation focuses on closed knight tours. A knight will be able to complete a closed knight’s tour iff it visits all vertices of the chessboard and finishes on a square adjacent to its starting square. This makes the knight’s tour a problem concerning Hamiltonian paths and Hamiltonian cycles.

This problem can be approached by considering the chessboard as a graph, a network of points.

A graph G (j, k) is defined on jk vertices. This is constructed by considering each square as a vertex, and then joining the vertices by edges if they are connected by a knight’s move (making them adjacent). It is easy to see that this graph is a bipartite graph, because each vertex can be split into two different groups – (x, y) can be white or (x, y) can be black; every white vertex is connected to a black vertex, making this graph bipartite. In fact, due to the Knight’s movement, every chess board can be shown to be a bipartite graph, because a Knight only moves from one square of one colour to another square of different colour.

For the purposes of this investigation, Schwenk’s Theorem must be used. Schwenk asserted that there is a closed knight’s tour on any j ∗ k, with j ≤ k, chessboard unless -

• j = 1, 2 or 4
• j and k are both odd;
• j = 3 and k = 4, 6 or 8

It will now be shown why these conditions do not allow for knight’s tours.

• If j = 1 or 2, it is immediately obvious that no knight’s tour is possible. This is due to the knight’s movement.

For j = 4, the case can be proven by considering that a knight starts on square R₁. Assume that from this square, the knight can move to squares R₂, R₃ or R₄. R₁ is connected via an edge to R₂ and R₃. R₂ and R₃ are connected by an edge. The number of squares and the number of moves is even. Visiting an even number of vertices without passing through the edge connecting R₂ and R₃ will always lead to the knight ending at either R₂ or R₃. However, the edge linking R₂ and R₃ must be taken.

This situation can be shown and proven graphically in the following diagrams -

Theorem.

Any tour starting on a grey square must visit all grey squares before a white square Proof. A name will be assigned to each vertex in fig. 4, going clockwise: V₁,V₂, V₃,V₄. In this proof, the number of times the knight passes through the edge between V₁ and V₂ is denoted by n(E₁). The other edges (going clockwise) are denoted by n(E₂) and n(E₃). The number of times each V_x is visited is shown by C_x. Of course, for a knight’s tour, C₁ = C₂ = C₃ = C₄ = 1 and n(E₁), n(E₂), n(E₃), C₁, C₂, C₃, C₄ ∈ Z⁺.

It will be assumed that the Knight starts from V₁; therefore, there are two possibilities to consider -

• if the circuit starts from V₁ and ends on V₁, then the reader can easily convince himself by looking at fig. 4 that: \(C_1=1+|\frac{n(E_1)}{2}|\), (because the Knight has to go all the way to V₄ and back to V₁) \(C_2=|\frac{n(E_1)}{2}|+ |\frac{n(E_2)}{2}|\), \(C_3=|\frac{n(E_2)}{2}|+|\frac{n(E_2)}{2}|\), \(C_4 = |\frac{n(E_3)}{2}|\). E₁, E₂ and E₃ are even, since these tours can only be even (see Theorem 2). By symmetry, it can then be seen that C₃ = C₄ (this is always true for Knight’s tours, which, by definition, involve the Knight visiting each vertex exactly once); \(C_3=C_4⟹|\frac{n(E_2)}{2}|+|\frac{n(E_3)}{2}|=|\frac{n(E_3)}{2}|⟹|\frac{n(E_2)}{2}|=0⟹n(E_2) = 0\) which is a contradiction.
• if the circuit starts from V₁ and ends on V₄, then E₁, E₂ and E₃ are odd (because the Knight only needs to travel through them once to arrive at V₄, and this can be very easily seen from fig. 4) and \(C_1=\frac{E_1+1}{2}\), \(C_2= \frac{E_1+E_2}{2}\), \(C_3=\frac{E_2+E_3}{2}\) and \(C_4=\frac{E_3+1}{2}\). Since the Knight only has to travel through V₁ and V₂ once, C₁ = C₂ and \(C_3 = C_4 ⟹ \frac{E_2+E_3}{2}=\frac{E_3+1}{2}⟹E_2=1\).

This is proof that in order to have a closed knight’s tour, the Knight must start at V₁ and E₂ must be traverse exactly once.

Obviously, since V₁ and V₃ are not directly connected, E₂ must occur after E₁. Therefore, the Knight must tour all the grey squares before passing through the white squares.

Since R₃ is connected to both R₁ and R₄, the tour will end on either R₁ or R₄. However, the tour started on R₁, and since R₁ and R₄ are not connected there is no way of making a closed tour.

• If j and k are odd, then the order of the Graph jk must also be odd. The order of the graph is the number of vertices on the graph. However, a bipartite graph cannot contain odd cycles. Proving this will prove point 2. of Schwenk’s Theorem.

Theorem.

A graph can only be bipartite if and only if it has no odd cycle Proof. If G is a bipartite graph, with bipartition X,Y of the vertices, every cycle C has vertices which alternate between X and Y. The cycle on a chessboard is closed since a chessboard has boundaries, therefore C has an even number of vertices and is even.

It is useful to prove this result in the case when G is a connected graph, as is the case with knight’s tours. The vertices of the graph G can be divided into two categories -

A will denote the vertices such that the shortest path from every vertex in A to v is of odd length, i.e., this path goes through an odd number of edges, including repeated edges.

B will represent the set of vertices for which the shortest path from any vertex in B to v is of even length.

The definition of a bipartite graph is that G = (V, E), where V represents the vertices of the Graph, and E represents its edges; V = A ∪ B and A ∩ B = ∅; all edges e ∈ E of the graph are of the form (a, b), where a ∈ A and b ∈ B.

Assume G has no odd cycle. Consider any vertex v ∈ G.

Of course, v ∈ B (because otherwise they would not be connected to each other by a path) and A ∩ B = ∅, since otherwise there would be a path of both even and odd length, which is clearly impossible. Without loss of generality, now, we introduce, referring to the matrix system introduced previously, two squares of the graph G, 1,1 and 1,2, which are adjacent, and 1,1 and 1,2 ∈ A. In a bipartite graph, this means that there is an edge of the graph on which both squares are incident, i.e. they meet that same edge.

Referring back to our definition of the set of vertices A, there would be a closed cycle of odd length, symbolically represented by v,... , 1,1, 1,2, ... , v). 1,1 and 1, 2 are next to each other because, as stated previously, they share the same edge.

But then, this would mean that G would contain a path of odd cycle. This is a contradiction to the initial assumption that G contains no odd cycles, and there cannot be two vertices in A which are adjacent. This example was made without loss of generality, and indeed the same condition applies to two vertices in B. Therefore, G = (A ∪ B,E) is bipartite. Therefore, X, Y is a valid bipartition and G is bipartite.

Hence, it is proven that there are no closed Knight’s tours on a chessboard where j and k are odd.

• To prove this, we first consider that the result for k = 4 was proven in part 1. of this section, to which the reader is reminded.

The case k = 6 can be shown using a graphical method.

It can be seen immediately that no closed tour is possible for a 3 × 6 board. Since we are working towards a closed Knight’s tour, 2,1 must be linked with 2,5, and these two must be connected with 1,3 and 3,3. However, it is impossible for a Knight’s tour to achieve so, since there would be a closed loop, effectively creating a four–move short circuit composed of these four squares.

Therefore, there is no Knight’s tour on a 3 × 6 chessboard.

For the instance k = 8, a similar graphical approach can be considered.

A B C D E F G H

I J K L M N O P

Q R S T U V W X

The inexistence of a Knight’s tour for a 3 × 8 chessboard is shown by contradiction. Assume that such a tour does exist. We begin our analysis of possible moves in the tour by noting that in the cases where a square is connected to only two other vertices of the graph, one of the two squares and the square must be part of the tour, for example H → N or H → W. We could also say that the passage through any of the three squares in the first column or any of the three in the last column is fixed.

Considering the above diagram, which shows algebraically a 3 × 8 chessboard, it can be seen that no tour containing both B → L and R → L is possible. This is because otherwise the result would be the closed loop A → R → L → B → Q → K → A. Other routes are equally ineffective in producing a Knight’s tour due to the geometry of the 3 × 8 configuration. Now, we can say that B → L is not a move in the tour; then, B → S must be (B → Q leads to the previous closed loop).

Similarly, we can say that R → C is not a move in the tour, as this would lead to the closed loop B → S → I → C → R → L → B.

Further, neither M → W nor M → G are both moves in the tour, as then M → G → X → N → H → W → M would be a closed tour. Therefore, from M the Knight must go to C.

Finally, both D → U and E → T, because as shown in the diagram below, only U and T are free squares from D and E respectively. However, this leads to the closed loop J → D → U → O → E → T → J. All other combinations of moves lead to open tours or no tour at all. Thus, there is no closed tour on a 3 × 8 chessboard.

Now that all the restrictions on Knight’s tours with 3 × k dimensions have been proved, we can show that there always are closed tours for all k ≥ 10.

This is achieved using a proof by complete induction.

Proposition:there exists a closed Knight′s tour for every board of size 3 × k, where k ≥ 10, n ∈ Z⁺, n ≠ 2q + 1, q ∈ Z.

There exist no closed Knight′s tours for all 1 ≤ k ≤ 9, k ∈ Z⁺

Base case:there exists a closed Knight′s tour for k = 10

Base case:there exists a closed Knight′s tour for k = 12

In section 1 of the paper it was shown that there exist no such tours for any 1 < k < 10.

For this proof, we must consider the fact that if we want to prove that a closed Knight’s tour exists for all boards j × k, k ≥ 10, then it must also exist for all boards j × (k + 4), k ≥ 10. This is because, considering solely our base case k = 10 or our base case k = 12, we cannot prove that closed tours exist for all k, however, having shown that at least one closed tour exists for k = 10 and k = 12, if we can prove that closed tours exist for all (k + 4) then we must have shown that there are tours for all possible values of k, k ∈ Z⁺. This is because every Z ≥ 10, Z ≠ 2q + 1 can be expressed in one of the two following forms: 10 + 4q or 12 + 4q, q ∈ Z.

Hence

Inductive step: having proved that no tours exist for 1 < k < 10, and assuming that, for n ≥ 10,it is true that at least one closed tour exists in a 3 × k board, a j × (k + 4) tour also exists -

We first consider an open tour in a 3 × 4 board, shown symbolically as a matrix below -

Now, consider a Knight moving in a 3 × 8 chessboard -

A B C D E F G H

I J K L M N O P

Q R S T U V W X 

Supposing that a Knight moves into square X, the 3 × 4 board can be adjoined to the 3 × 8 board, enabling the Knight to jump from X to α or θ -

\(\begin{array}{cccccccccccccccccccc} A & B & C & D & E & F & G & H &&&&\alpha & \beta & \gamma & \delta \\I & J & K & L & M & N & O & P &&+&&\epsilon & \theta & \mu& \pi \\ Q & R & S & T & U & V & W & X& && & \rho & \sigma & \tau & φ \\ \end{array} \)

Therefore, if the Knight were to reach either corner of the 3 × k (in this case 3 × 8) board, where 1 ≤ k ≤ 9, then jump onto the 3 × 4 board, perform an open Knight’s tour on such board and then return to the 3*k board, it would perform a closed tour.

If we assume that a 3 × k closed tour exists,then a 3 × (k + 4) closed tour also exists for k ≥ 10.

It was shown that the proposition is true for k = 10 and k = 12.

The proposition is true for k = 10 and k = 12 and, since it is true for 1 ≤ k ≤ 9,then it is also true for k ≥ 10.

Hence the proposition is true for all k ≥ 10, k = 2n, by the principle of complete induction.

The results for the number of closed tours for 3 × 2k, k ∈ Z⁺, tours are summarised below. These figures include tours obtained by reflection and rotation of the chessboard.