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.

Let un be the number of closed Knight’s tours for 3 × 2k boards. Here, n stands for k, for example n = 23 actually refers to a 3 × 46 chessboard, since 3 × (2 × 23) = 3 × 46; we could also say that n denotes double the number of columns in a particular chessboard. It can be shown that the number of closed Knight’s tours for 3 × 2k boards is given by the recurrence relation -

 

u_n = 6u_{n − 1} + 64u_{n − 2} − 200u_{n − 3} − 1000u_{n − 4} + 3016u_{n − 5} + 3488u_{n − 6} − 24256u_{n − 7} + 23776u_{n − 8} + 104168u_{n − 9} − 203408u_{n − 10} − 184704u_{n − 11} + 443392u_{n − 12} + 14336u_{n − 13} − 151296u_{n − 14} + 145920u_{n − 15} − 263424u_{n − 16} + 317440u_{n − 17} + 36864u_{n − 18} − 966656u_{n − 19} + 573440u_{n − 20} + 131072u_{n − 21}, n ≥ 23

 

The starting values of this recurrence relation are given in the table above.

 

Proposition:the sequence for closed Knight′s tours on 3 × 2k, k ∈ Z⁺, boards is defined by the recurrence relation

 

u_n = 6u_{n − 1} + 64u_{n − 2} − 200u_{n − 3} − 1000u_{n − 4} + 3016u_{n − 5} + 3488u_{n − 6} − 24256u_{n − 7} + 23776u_{n − 8} + 104168u_{n − 9} − 203408u_{n − 10} − 184704u_{n − 11} + 443392u_{n − 12} + 14336u_{n − 13} − 151296u_{n − 14} + 145920u_{n − 15} − 263424u_{n − 16} + 317440u_{n − 17} + 36864u_{n − 18} − 966656u_{n − 19} + 573440u_{n − 20} + 131072u_{n − 21}, n ≥ 23

 

Base case - n = 23

 

Using Wolfram|Alpha -

 

6 × 2085233793265765376 + 64 × 214282979451801088 - 200 × 22020130538878208 - 1000 × 2262837745837568 + 3016 × 232533011307776 + 3488 × 23895692937216 - 24256 × 2455552258304 + 23776 × 252338724352 + 104168 × 25931157504 - 203408 × 2664515712 - 184704 × 273895232 + 443392 × 28120096 + 14336 × 2896832 - 151296 × 295456 + 145920 × 30848 - 263424 × 3072 + 317440 × 352 + 36864 × 32 = 20291876152214982656.

 

So the proposition is true for n = 23

 

The other base cases were similarly checked using Wolfram|Alpha, so the proposition is true for all base cases.

 

Suppose that we have checked and proved the proposition for all n < K, and are now looking at n = K -

 

u_K = 6u_{K − 1} + 64u_{K − 2} − 200u_K−3 − 1000u_{K − 4} + 3016u_{K − 5} + 3488u_{K − 6} − 24256u_{K − 7} + 23776u_{K − 8} + 104168u_{K − 9} − 203408u_{K − 10} − 184704u_{K − 11} + 443392u_{K − 12} + 14336u_{K − 13} − 151296u_{K − 14} + 145920u_{K − 15} − 263424u_{K − 16} + 317440u_{K − 17} + 36864u_{K − 18} − 966656u_{K − 19} + 573440u_{K − 20} + 131072u_{K − 21}

 

The expression

 

u_n = 6u_{n − 1} + 64u_{n − 2} − 200u_{n − 3} − 1000u_{n − 4} + 3016u_{n − 5} + 3488u_{n −  6} − 24256u_{n − 7} + 23776u_{n − 8} + 104168u_{n − 9} − 203408u_{n − 10} − 184704u_{n − 11} + 443392u_{n − 12} + 14336u_{n − 13} − 151296u_{n − 14} + 145920u_{n − 15} − 263424u_{n − 16} + 317440u_{n − 17} + 36864u_{n − 18} − 966656u_{n − 19} + 573440u_{n − 20} + 131072u_{n − 21}

 

is valid for n = K − 1, n = K − 2, ... , n = K − 23

 

This leads to a very complicated expression in which one expression is nested into the others 23 times. Having access to more powerful software would enable me to show the full proof of the proposition. The programs available to me are not able to cope with all the mathematical expressions involved.

 

So the statement is true for n = K.

 

The proposition

 

un = 6u_{n − 1} + 64u_{n − 2} − 200u_{n − 3} − 1000u_{n − 4} + 3016u_{n − 5} + 3488u_{n − 6} − 24256u_{n − 7} + 23776u_{n − 8} + 104168u_{n − 9} − 203408u_{n − 10} − 184704u_{n −11} + 443392u_{n − 12} + 14336u_{n − 13} − 151296u_{n − 14} + 145920u_{n − 15} − 263424u_{n − 16} + 317440u_{n − 17} + 36864u_{n − 18} − 966656u_{n − 19} + 573440u_{n − 20} + 131072u_{n − 21}

 

is true for n = 23 and,is true for all n < K then it is also true for n = K.

 

Hence the proposition is true for all n by the principle of complete induction.

This part of the investigation focuses on finding the proportion of closed Knight’s tours in 3 × 2k boards by comparing the number of closed Knight’s tours to the number of open Knight’s tours in irregular chessboards of size described above.

 

The table below shows the number of undirected open Knight’s tours. The figures were obtained by using some known values, however, the number of closed knight’s tours had to be subtracted from each value, since the data used included both open and closed tours.

By dividing the number of closed tours by the number of open tours (because by definition open tours include closed tours), a graph for the relationship between the proportion of closed tours given that the Knight will

perform a tour on a 3 × 2k chess board and the number of columns can be obtained: the curve can be modelled by choosing three points on it. This is because it is speculated that the curve is exponential in nature, therefore it might satisfy a relation of the kind y = Ae^Bx + C.

 

This is because, plotting a graph of ln (proportion of closed tours) against Number of columns, a straight line with r² = 0.985 is obtained, hence r = 0.992. Since 0 ≤ r ≤ 1, where 1 denotes a fit which perfectly denotes the data, it is presumable that an exponential curve is a very good model for the points obtained.

Three points from the first graph were selected in order to determine the constants A,B and C. The three equations are -

 

0.000224 = Ae^16B + C          (1)

 

0.000110 = Ae^20B + C          (2)

 

4.24 × 10−5 = Ae^26B + C          (3)

 

(1) − (2) ⟹ 0.000114 = A(e^16B − e^20B)          (4)

 

(2) − (3) ⟹ 0.0000676 = A(e^16B − e^20B)          (5)

 

\(\frac{(4)}{(5)} ⟹1.69 = \frac{e^{16B} \,− \,e^{20B}}{ e^{20B}− \,e^{26B}}⟹ B = −0.192\) using GDC: Grapher → Plot of both graphs → Intersection.

 

Substituting the values in equation (4) ⟹ A = 0.00459 using GDC: Calculate → Algebra → Numerical Solve.

 

Finally, Substituting the values for A and B in equation (1) ⟹ C = 0.0000113

 

Therefore, the fitted curve for the first graph is y = 0.00459e^−0.192x + 0.0000113

 

Comparing the equation obtained from the data fitting with the equation Excel gives, it can be seen that the fitting was probably not a good model for the curve, since the values for the constants come out to be quite different. This inaccuracy is justified by the fact that the method used to determine the equation of the curve only considered three points, while the Excel program considers all points on the curve to determine its equation; this is important, because it can be seen from the first graph that the 3 × 10 chess board represents an anomaly, thus the true equation of the curve is much different from that obtained. The 3 × 10 board may be an anomaly because the effective “domain” of the  3 × 10 boards which allow for closed Knight’s tours starts at 10.

 

The validity of this fit will be examined. Substituting values for x into the equation y = 0.00459e − x = 18 ⟹ y = 0.000156 using GDC: Calculate→Algebra→Numerical Solve.0.192x + 0.0000113 for x = 10, x = 12, x = 14 and x = 18 yields -

 

x = 10 ⟹ y = 0.000684 using GDC - Calculate → Algebra → Numerical Solve.

 

x = 12 ⟹ y = 0.000470 using GDC - Calculate → Algebra → Numerical Solve.

 

x = 14 ⟹ y = 0.000323 using GDC - Calculate→Algebra→Numerical Solve.

 

x = 18 ⟹ y = 0.000156 using GDC - Calculate→Algebra→Numerical Solve.

 

Now, the percentage error for each of these figures will be calculated using the formula -

 

\(percentage error =\frac{\text{|experimental value - actual value|}}{\text{|actual value|}}× 100,\)

 

where the actual value is the value displayed by the points on the first graph.

 

\(\text{percentage error}_{x≡10} =\frac{|0.000684 − 0.00106|}{0.00106} × 100 = 35\%\)

 

\(\text{percentage error}_{x≡12} = \frac{|0.000470 − 0.000516|}{0.000516} × 100 = 8.9\%\)

 

\(\text{percentage error}_{x≡14} =\frac{|0.000323 − 0.000341|}{ 0.000341} × 100 = 5.3\%\)

 

\(\text{percentage error}_{x=18} =\frac{ |0.000156 − 0.000155|} {0.000155} × 100 = 33\%\)

 

What emerges is that the model probably isn’t a valid representation of the true curve since the percentage errors are quite large.

It is fair to say that the mathematical tools used have enabled me to reach the aim of my exploration, as I have been able to fully derive the relationship between my two variables. I decided to estimate my answer’s accuracy by calculating its percentage error, because I think this gives a good indication of the quality of my work. It can be said that the accuracy of my answer is most likely not good enough, given the large percentage error on most values considered. The errors in the fitted equation compared to the equation given by Microsoft Excel are probably due to the fact that Excel uses all the points on the graph to compute an equation, thus giving a more accurate result. Anyway, to improve on this part of the exploration, it would have been beneficial to plot more points with greater values for the number of columns, to obtain an even more reliable equation.

 

Overall, I have developed a number of skills through this investigation. One of the major issues I encountered during the investigation was in understanding the concepts underpinning the Knight’s tour problem before actually progressing to tackle it. However, using highly analytical sources, I have massively improved my mathematical reasoning, since I have successfully understood the proofs involved in this exploration, and indeed I have gone above and beyond them, trying as best as I could to explain them to the interested reader. This enhanced my critical thinking, as I did much more than just copy the proofs onto my investigation. Moreover, this exploration very much enhanced my understanding of graph theory, strong induction and recurrence relations, and, more generally, of Discrete Mathematics, a branch of Mathematics which I knew very little of before starting this investigation.

 

I believe that these new techniques have been very beneficial for my report because they have enabled me to gain a real appreciation of the Mathematics behind this fascinating puzzle; for instance, knowing that a recurrence relation for the number of tours is valid for all numbers of columns was very useful in guiding me on to the next part of my exploration, and creating a model to show the relationship between the proportion of closed Knight tours as a function of the number of columns in a chess board, which is, even though restricted in scope, nevertheless correct.

 

Looking at the relationship between the number of closed Knight’s tours and the increasingly bigger number of columns for fixed rows, I thought that the relationship between them seems very plausible, since with a greater number of columns, there would logically be a greater number of tours, however the increase in the amount of tours is greatly outweighed by the number of further moves of the Knight given more columns. However, the relationship obtained is probably not accurate, since the number of columns considered was only small (up to thirty). Possibly, a larger number of columns would have been better for more reliable analysis.

 

To obtain more information about the frequency of Knight’s tours, it would have been more useful to know the total number of possible Knight moves, starting from any square – unfortunately, this is a very difficult task to achieve. This would certainly have improved the investigation. A similar extension to the problem would have been to attempt to better explain the nature of the negative relationship between the logarithm of the proportion and the number of columns. Possibly, this is due to the nature of the recurrence relations associated with them. Another possible idea for improvement or extension would be to look at the number of unique (geometrically distinct) Knight’s tours, therefore excluding those obtained via reflections or rotations of the chess board.

 

This investigation has been significant for me; not only has it further enhanced my passion for chess, but it also has made me significantly more eager to better understand the complex and fascinating topic of graph theory, and perhaps, by researching more into the topic, to even develop computer algorithms to be used to aid me with numerical calculations with big numbers, or for simulations of Knight’s tours, so that the more theoretical and mathematical parts of similar investigations could be better visualised. I think that a possible application of this report would be in the Hamiltonian path problem18 for more complicated graphs, for example by applying techniques similar to those used in this exploration to more complex boards with a greater number of rows, of even 3 - D boards.

• “1.5 - The Coefficient of Determination, r-Squared.” 1.5 - The Coefficient of Determination, r - Squared | STAT 501, onlinecourses.science.psu.edu/stat501/node/255/. First Accessed December 10 2018
• “Bipartite Graph Characterization.” Graph Fundamentals, Prof. Kindred, www.math.hmc.edu/~kindred/cuc-only/math104/lectures/lect03.pdf First Accessed December 9 2018
• Elkies, N. D. and Stanley, R. P. "The Mathematical Knight." Math. Intell. 25, No. 1, 22-34, Winter 2003. First Accessed December 9 2018
• Ganzfried, Sam, and Paul Cull. A SIMPLE ALGORITHM FOR KNIGHT’S TOURS. Oregon State University, 2004, math.oregonstate.edu/~math_reu/proceedings/REU_Proceedings/Proceedings2004/2004Ganzfried.p df. First Accessed December 9 2018
• “Graph Is Bipartite Iff No Odd Cycles.” Time of Travel down Brachistochrone - ProofWiki, proofwiki.org/wiki/Graph_is_Bipartite_iff_No_Odd_Cycles. First Accessed December 9 2018
• “Knight Graph.” From Wolfram MathWorld, mathworld.wolfram.com/KnightGraph.html. First Accessed December 9 2018
• Knight's Tours, gaebler.us/share/Knight_tour.html. First Accessed December 12 2018
• “Knight's Tours of Three-Rank Boards.” Biography: W. K. Clifford, First Accessed December 12 2018
• https://www.mayhematics.com/t/ob.htm.%20First%20Accessed%20December%209%202018
• Knight’s Tour - Oregon State University. math.oregonstate.edu/~math_reu/proceedings/REU_Proceedings/Proceedings2002/2002AL_McGow n.pdf. First Accessed December 9 2018
• Lazdans, Edvards. “Possible Chess Knights Movements Using Minimax Algorithm.” Custom Software Development, Diatom Enterprises, 31 Oct. 2018, www.diatomenterprises.com/ruby-and- recursion-find-out-all-possible-chess-knights-movements-using-minimax-algorithm/. First Accessed December 9 2018
• List of LaTeX Mathematical Symbols - OeisWiki, oeis.org/A158074. First Accessed December 9 2018
• List of LaTeX Mathematical Symbols - OeisWiki, oeis.org/A169696. First Accessed December 9 2018
• Stanley 1999, Ch. 4.7; Elkies and Stanley 2003 First Accessed December 10 2018
• Variable Naming Conventions, www.cs.toronto.edu/~arnold/492/ParallelAlgorithms/commentedReport/node12.html. First Accessed December 12 2018
• Which Rectangular Chessboards Have a Knights Tour? www.math.cmu.edu/~nkomarov/21- 110/knighttour.pdf. First Accessed December 9 2018