Chess is one of the oldest and most popular board games. Computer
scientists have been interested in the game for many years and thus computer
chess came into being. However, computer scientists are also interested in
several puzzles that are not directly related to playing chess but use some concepts
and constructs of the game instead. The most famous of them are the
n-queens problem and the knight's tour problem
(Brassard and Bratley, 1996; and Cormen et
al., 2001). This paper introduces another such problem called the knight's
reach problem. The knight's reach problem is a logical puzzle meant for `recreation'
of computing community. The problem can also be used as an exercise in courses
on programming and algorithms.
(Knight's Reach Problem): Given a chessboard that
is infinite in both dimensions and containing no pieces except for a knight. The
problem is to find the squares that the knight can reach after n moves.
A knight has an L-shaped move. On an infinite and vacant chessboard, a
knight always has eight options to move (Figure
1). Let a typical square on the chessboard be represented as
(x, y) and the square where the knight is initially positioned
be considered as (0, 0).
The knight's reach problem was implemented and solved by
calculating the sets Kn, Cn and Qn. Observations
were noted for different values of n. Table
1 enumerates the sets Kn, Cn and Qn for n = 0, 1 and 2. Appendix 1 plots Kn and Cn whereas Appendix 2 plots Qn for n = 0 to 5. It was observed that the sizes of the
sets Kn and Cn increase geometrically
while the size of the set Qn increases arithmetically with the increase in n
This paper has introduced and briefly analyzed the knight's reach problem. It
is expected that efficient algorithms for solving the knight's reach problem will
be developed using dynamic programming and backtracking. |
