Free puzzles / Question / The Guarded Chessboard
The Kennel Puzzle.
A man has twenty-five dog kennels all communicating with each other by
doorways, as shown in the illustration. He wishes to arrange his twenty
dogs so that they shall form a knight's string from dog No. 1 to dog No.
20, the bottom row of five kennels to be left empty, as at present. This
is to be done by moving one dog at a time into a vacant kennel. The dogs
are well trained to obedience, and may be trusted to remain in the
kennels in which they are placed, except that if two are placed in the
same kennel together they will fight it out to the death. How is the
puzzle to be solved in the fewest possible moves without two dogs ever
being together?
Answer
Call one pawn A and the other B. Now, owing to that optional first move,
either pawn may make either 5 or 6 moves in reaching the eighth square.
There are, therefore, four cases to be considered: (1) A 6 moves and B 6
moves; (2) A 6 moves and B 5 moves; (3) A 5 moves and B 6 moves; (4) A 5
moves and B 5 moves. In case (1) there are 12 moves, and we may select
any 6 of these for A. Therefore 7x8x9x10x11x12 divided by 1x2x3x4x5x6
gives us the number of variations for this case--that is, 924. Similarly
for case (2), 6 selections out of 11 will be 462; in case (3), 5
selections out of 11 will also be 462; and in case (4), 5 selections out
of 10 will be 252. Add these four numbers together and we get 2,100,
which is the correct number of different ways in which the pawns may
advance under the conditions. (See No. 270, on p. 204.)