Moving Knights on a ChessboardDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/