Moving Knights on a Chessboard

Date: 01/27/99 at 22:13:54
From: Tasha Gibson
Subject: 4 knights, and a 3*3 chess board

Strict rules determine how knight pieces may move on a chessboard. Each 
"move" consists of two squares in one direction and then one square in 
a perpendicular direction. The rules also state that no two chess 
pieces may occupy the same square at the same time, although knights 
may pass or jump over the other pieces on the way to an empty square. 
One day two black knights and two white knights were sitting around on 
a 3-by-3 chess board, one in each corner. To liven things up they 
decided to switch places, so that the white knights would end up where 
the black knights started out and vica versa. Unfortunately, they could 
move only one at a time, according to the rules described above. And 
they had to stay within the nine squares of their board. 

1. Can they do it? Yes.

2. If so, what is the least number of moves it will take them to 
   switch, and how do you know this number is the least? 

3. If it is not possible, explain why.

Date: 01/28/99 at 05:10:52
From: Doctor Allan
Subject: Re: 4 knights, and a 3*3 chess board

Hi Tasha,

Nice question, isn't it? Let's start by labeling the squares of the 
chess board:

   -------------
   | 1 | 2 | 3 |
   -------------
   | 4 | 5 | 6 |
   -------------
   | 7 | 8 | 9 |
   -------------

If a knight is positioned in square 1, for instance, it can jump to 
squares 6 or 8. Similarly with the other squares. If we let -> mean 
'can jump to' we can list all possible jumps from all the squares:

  1  ->  6,8
  2  ->  7,9
  3  ->  4,8
  4  ->  3,9
  5  ->  none of the squares
  6  ->  1,7
  7  ->  2,6
  8  ->  1,3
  9  ->  2,4

We can now make the following list of jumps such that in this list the
knight will only take one step at a time:

   -------------------------------------
   |   |   |   |   |   |   |   |   |   |   
   -------------------------------------
     8   1   6   7   2   9   4   3   8


Here the first and the last fields are the same such that squares 3 and 
8 are'glued together'. This list is made in accordance with the above 
list of possible jumps. For example - if you are in square 7 in this 
list you can go left to square 6 or right to square 2. That's exactly 
the possible jumps from square 7 in the first list.

Now let's say that the black knights were in squares 1 and 3 to begin 
with and the white knights in squares 7 and 9. Then our list looks like 
this:

   -------------------------------------
   |   | B |   | W |   | W |   | B |   |
   -------------------------------------
     8   1   6   7   2   9   4   3   8

You just need to move the knights to the right until they have 
exchanged places. Let me give you some examples. First move the black 
knight one square 3 to square 8:

   -------------------------------------
   | B | B |   | W |   | W |   |   |(B)| 
   -------------------------------------
     8   1   6   7   2   9   4   3   8

Then move the white knight from square 9 to square 4:

   -------------------------------------
   | B | B |   | W |   |   | W |   |(B)|
   -------------------------------------
     8   1   6   7   2   9   4   3   8

Now move the white knight from square 7 to square 2:

   -------------------------------------
   | B | B |   |   | W |   | W |   |(B)|
   -------------------------------------
     8   1   6   7   2   9   4   3   8

and then the black knight from square 1 to square 6:

   -------------------------------------
   | B |   | B |   | W |   | W |   |(B)|
   -------------------------------------
     8   1   6   7   2   9   4   3   8

I finished moving all the knights once. Now continue this way until you 
have white knights on squares 1 and 3 and black knights on squares 7 
and 9. It should take 16 moves in all (including the above 4).

I hope this helps,

- Doctor Allan, The Math Forum
  http://mathforum.org/dr.math/