![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
A -knight’s move on the
cylinder chessboard is the move of the knight 2 squares vertically or 2 squares horizontally and then 3 squares perpendicular to it. In this paper, we show a closed
-knight’s tour on the
cylinder chessboard for all positive integers
and
, and a closed
-knight’s tour on the
cylinder chessboard for all positive integers
and
. Moreover, we show that there is no closed
-knight’s tours on the
cylinder chessboard where (i)
and (ii)
and
.
1 Introduction and preliminaries
The chessboard is an array with
rows and
columns. A legal knight’s move is the moves from one square vertically or one square horizontally and then two squares perpendicular to it. A question of the
chessboard is “which chessboard that the knight can move to all squares of the chessboard exactly once and return to the starting square?” The knight’s moves that move to all squares of the chessboard exactly once and return to the starting square is called a closed knight’s tour. The answer of this question was obtained by Schwenk Citation[1] in 1991 as follows.
Theorem 1
Citation[1] The chessboard with
admits a closed knight’s tour unless one or more of the following conditions hold :
(i) and
are both odd;
(ii) , or
; or
(iii) and
or
.
In 2005, Chia et al. Citation[2] generalized the legal knight’s move to an -knight’s move. That is, the knight can move
squares vertically or
squares horizontally and then
squares perpendicular to it. Then, the legal knight’s move is a
-knight’s move. The problem is similar to the legal knight’s move. The
-knight’s moves that move to all squares of the chessboard exactly once and return to the starting square is called a closed
-knight’s tour. The authors in Citation[2] obtained the following result for the
-knight’s move.
Theorem 2
Citation[2] The chessboard where
admits a closed
-knight’s tour if and only if
(i) |
| ||||
(ii) |
| ||||
(iii) |
| ||||
(iv) |
|
The knight’s tour problem was discussed in the cylinder chessboard. We can think of creating the
cylinder chessboard by starting with an
chessboard and then joining the left end with the right end. In Citation[3], Watkins obtained the following result.
Theorem 3
Citation[3] An cylinder chessboard has a closed knight’s tour unless one of the following two conditions holds: (a)
and
; or (b)
or
and
is even.
In this paper, we consider a -knight’s move on the cylinder chessboard. A closed
-knight’s tour on the
cylinder chessboard for all positive integers
and
, and a closed
-knight’s tour on the
cylinder chessboard for all positive integers
and
are shown in Theorems 6 and 8, respectively. Moreover, we show that the
cylinder chessboard, where
contains no closed
-knight’s tours (in Theorem 5) and the
cylinder chessboard, where
, also contains no closed
-knight’s tours (in Lemma 2).
2 Main results
For an cylinder chessboard, we start with an
chessboard. When we consider the
cylinder chessboard with an
chessboard, let each square be
where
is counting in the matrix fashion. If the knight stands at
, then the knight can move to at most eight squares :
and
where
and
are in modulo
.
The knight’s tour problem can be considered by using a graph. Let be a graph with
. Two vertices,
and
, are adjacent if the knight can move from
to
. Then, a closed
-knight’s tour is a Hamiltonian cycle of a graph
, a cycle of
that contains all vertices of
.
Before proving the main results, we need the following well-known result concerning Hamiltonian cycle (see for example Citation[4]).
Theorem 4
Let be a proper subset of the vertex set of a graph
. If
contains a Hamiltonian cycle, then
contains at most
components.
If is a graph and
is a subset of
, let
denote a subgraph of
induced by
.
Theorem 5
Suppose that and
. Then, the
cylinder chessboard contains no closed
-knight’s tours for any positive integer
.
Proof
Let be a graph representing the
cylinder chessboard.
Case 1: . If
, then
is a disconnected graph. Thus, it has no closed
-knight’s tours. Next, let
.
If or
, then the degree of vertices
is
. Then,
contains no Hamiltonian cycle.
If and
, then we consider vertices in the 2nd row. Since, for
, vertex
in the 2nd row is adjacent to vertices
and
where
(mod
) and
(mod
), the degree of each vertex in the 2nd row is
. If
contains a Hamiltonian cycle, then such two edges that incident with each vertex in the 2nd row must be in the Hamiltonian cycle. We see that edges incident with vertices in the 2nd row form cycle which is not a Hamiltonian cycle. The cycle starts at
, goes on the right side of the chessboard and then returns to the left side of the chessboard until we end at the right side.
Case (i): (mod
). Let
for some positive integer
. The cycle is in the following form.
,
.
Case (ii): (mod
). Let
for some positive integer
. The cycle is in the following form.
,
,
.
Case (iii): (mod
). Let
for some positive integer
. The cycle is in the following form.
,
,
,
,
.
Case 2: .
Case 2.1: . Let
. Then,
.
If or
, let
be a subgraph of
induced by the set of vertices
and
where
. Then,
contains
and
isolated vertices from the 1st and 6th rows. By Theorem 4,
contains no Hamiltonian cycles. (See .)
If (respectively
), then
contains
(respectively
) components. shows the graph
where the white vertices are in
. By Theorem 4,
contains no Hamiltonian cycles.
Case 2.2: . Let
. Then,
and
contains
isolated vertices from the
and 7th rows. By Theorem 4,
contains no Hamiltonian cycles.
Case 2.3: . Let
. Then,
.
If is odd, let
be a subgraph of
induced by the set of vertices
and
where
. Then,
contains
and
isolated vertices from the 2nd and 7th rows. By Theorem 4,
contains no Hamiltonian cycles.
If is even, let
and
. Then,
contains
and
isolated vertices from 2nd and 7th rows. By Theorem 4,
contains no Hamiltonian cycles.
This completes the proof. □
Lemma 1
The cylinder chessboard admits a closed
-knight’s tour for any positive integer
.
Proof
Let be a positive integer. We give two patterns to construct a closed
-knight’s tour for the
cylinder chessboard. Since the total number of squares of the
cylinder chessboard is
, for each pattern, we start the first position at
labeled with number
. We define four directions of the knight’s move as follows.
means the knight moves two squares downward and then goes three squares to the right,
means the knight moves two squares downward and then goes three squares to the left,
means the knight moves three squares upward and then goes two squares to the right, and
means the knight moves three squares upward and then goes two squares to the left.
Then, we obtain two patterns of a closed -knight’s tour as follows.
For the 1st pattern, the first, second, third, fourth and fifth moves are and
, respectively. We repeat this algorithm for
times (see (a)).
For the 2nd pattern, the first, second, third, fourth and fifth moves are and
, respectively. We repeat this algorithm for
times (see (b)).
We obtain some observations as follows.
(i) For each loop, the starting point is on the 1st row,
(ii) the 1st number of each loop is where
,
(iii) squares labeled with the five consecutive numbers are on different rows, for example, squares labeled with and
stand in the 1st, 3rd, 5th, 2nd and 4th rows, respectively,
(iv) if is the first number of a loop and stands at
, then
is the first number of the next loop and stands at
if the knight move with the first pattern or at
if the knight move with the second pattern.
By the observation, the 1st number of each loop stands in the different squares. The 2nd, 3rd, 4th and 5th numbers of each loop are considered in similar way. Then, the knight moves to all squares exactly once and the number is on
if the knight move with the first pattern, or
if the knight move with the second pattern. Thus, the knight can move to the first position
. □
Theorem 6
The cylinder chessboard admits a closed
-knight’s tour for any positive integers
and
.
Proof
If , then a closed
-knight’s tour is obtained by Lemma 1. Suppose that
. The
cylinder chessboard is obtained from
copies of the
cylinder chessboards by putting each copy from the top to the bottom. We count all copies from the top to the bottom. Since each copy contains a closed
-knight’s tour, we combine each tour of each
cylinder chessboard to a single tour by deleting one edge from the top and the bottom and two edges from the
th cylinder chessboard for all
and then joining each piece to a single cycle.
Case 1 : . We give another pattern for the
cylinder chessboard which is different from the two patterns of Lemma 1 (shown in ).
If , then delete edge 2–3 of the
th copy, and edge 1–2 of
th copy and then join
(respectively
) of the
th copy to
(respectively
) of the
th copy for all
.
If or
, then delete edge 2–3 of the
th copy, and edge 6-7 of
th copy and then join
(respectively
) of the
th copy to
(respectively
) of the
th copy for all
.
If , then delete edge 2–3 of the
th copy, and edge 11–12 of
th copy and then join
(respectively
) of the
th copy to
(respectively
) of the
th copy for all
.
Case 2 : . If
, the
cylinder chessboard is obtained from
copies of the
cylinder chessboards by putting each copy from the top to the bottom. The top copy is assigned by the 1st pattern of a closed
-knight’s tour and the bottom copy is assigned by the 2nd pattern of a closed
-knight’s tour from Lemma 1. Thus, we combine each tour of each copy to a single tour by deleting edge
from the top and edge
from the bottom and then joining
to
and
to
.
Next, suppose that . The
cylinder chessboard is obtained from
copies of the
cylinder chessboards by putting each copy from the top to the bottom and counting all copies from the top to the bottom. If
is odd, then the
th copy is assigned by the 1st pattern of a closed
-knight’s tour from Lemma 1. If
is even, then the
th copy is assigned by the 2nd pattern of a closed
-knight’s tour from Lemma 1. Thus, we combine each tour of each copy to a single tour as follows.
1. Delete edge from the 1st copy and edge
from the
th copy.
2. For , delete edges
and
from the
th copy.
3. For , join
and
of the
th copy to
and
of the
th copy, respectively.
This completes the proof. □
illustrates closed -knight’s tours on 15 × 6 and 20 × 6 cylinder chessboards.
For the cylinder chessboard, we consider
.
Lemma 2
Let . Then, the
cylinder chessboard admits no closed
-knight’s tours.
Proof
Let and
be a graph representing the
cylinder chessboard. For
, let
and
n. Let
. Then,
and
contains
isolated from the 2nd and 8th rows,
and
where
. By Theorem 4,
contains no Hamiltonian cycles. □
Theorem 7
Let be an integer such that
. Then, the
cylinder chessboard admits a closed (2, 3)-knight’s tour if and only if
.
Proof
If , then by Lemma 2, the
cylinder chessboard admits no closed (2, 3)-knight’s tours. Closed (2, 3)-knight’s tours on the
cylinder chessboard where
are shown in . □
Theorem 8
Suppose that and
. Then, the
cylinder chessboard admits a closed
-knight’s tour for any positive integer
.
Proof
If , then a closed
-knight’s tour is obtained by Theorem 7. Suppose that
. The
cylinder chessboard is obtained from the
copies of
cylinder chessboards by putting each copy from the top to the bottom. We count all copies from the top to the bottom. Since each copy contains a closed
-knight’s tour, we combine each tour of each
cylinder chessboard to a single tour by deleting one edge from the top and the bottom and two edges from the
th copy where
and then joining each piece to a single cycle.
Case 1: . Delete edge 29–30 of the
th copy and edge 1–2 of the
th copy and then join
(respectively
) of the
th copy to
(respectively
) of the
th copy for all
.
Case 2: . Delete edge 12–13 of the
th copy and edge 1–2 of the
th copy and then join
(respectively
) of the
th copy to
(respectively
) of the
th copy for all
.
Case 3 : . Let
be a number
of
. Then, for each
, the number
or
is on
. Assume that
. Delete edge
of the
th copy and edge 1–2 of the
th copy and then join
(respectively
) of the
th copy to
(respectively
) of the
th copy for all
. □
illustrates closed (2,3)-knight’s tours on the ,
and
cylinder chessboards. In future research, we will try to see whether the
cylinder chessboard has a closed
-knight’s tour or not.
Acknowledgments
I would like to thank the referees for their comments and suggestions on the manuscript.
References
- SchwenkA.L., Which rectangular chessboards have a knight’s tour Math. Mag. 641991 325–332
- ChiaG.L.OngSiew-Hui, Generalized knight’s tours on rectangular chessboards Discrete Appl. Math. 1592005 80–98
- WatkinsJ.J., Knight’s tours on cylinders and other surfaces Congr. Numer. 1432000 117–127
- ChartrandG.ZhangP., A First Course in Graph Theory2005Mc Graw-Hill Higher EducationBoston