Ken's POTW 980720

Alexander's Knight Puzzle

In the computer game The 7th Guest, one of the memorable puzzles was, given a 4x5 chessboard (as below), place four black bishops on ABCD and four white bishops on abcd, then using only valid chess moves, move all the black bishops to abcd and the white bishops to ABCD. At no time may any piece be under attack by the opposite color. You might enjoy trying to solve this puzzle - it's not too difficult with a little trial and error.

 4x5 board
+--+--+--+--+--+
| A| 1| 5| 9| a|
+--+--+--+--+--+
| B| 2| 6|10| b|
+--+--+--+--+--+
| C| 3| 7|11| c|
+--+--+--+--+--+
| D| 4| 8|12| d|
+--+--+--+--+--+

The puzzle I'm more interested in is this: Alexander Doskey suggests you repeat this puzzle, using knights. Moves do not need to alternate in color.

Source: Reader Alexander Doskey.

Solutions were received from several people. Two with computer solutions found the shortest solution to require 32 moves. First the hand-solutions:

Michael Schooneveldt sent:

I did some tinkering and came up with the following solution.

1.  20-> 9      21. 15-> 4
2.  10->19      22. 11->18
3.   6-> 3      23.  1->12
4.  16->13      24.  5-> 8
5.  13-> 6      25.  8->11
6.  15-> 4      26. 12-> 1
7.   4-> 7      27.  6->17                      +--+--+--+--+--+
8.   7->16      28. 17->14                      | 1| 2| 3| 4| 5|
9.   9->20      29. 14-> 5                      +--+--+--+--+--+
10. 11->18      30. 10-> 3                      | 6| 7| 8| 9|10|
11. 18->15      31.  3-> 6                      +--+--+--+--+--+
12. 20-> 9      32.  1->12                      |11|12|13|14|15|
13.  9-> 2      33. 12->19                      +--+--+--+--+--+
14.  2->11      34. 19->10                      |16|17|18|19|20|
15. 16-> 7      35.  5->14                      +--+--+--+--+--+
16.  6->13      36. 11-> 8
17. 13->20      37.  8-> 1
18.  7->16      38. 18->11
19.  3-> 6      39.  4->15
20. 19->10      40. 14-> 5

Moves 1 - 20 transfer half the knights; moves 21 - 40, transferring the
other half, can then be inferred.

I (Ken) found a 44 move solution: b-12, B-4, D-2, d-7-b-5, 2-D, C-1-7, c-8-C, 7-9-c, D-7-d-10, 5-b-7-D, 10-d, C-1, c-9 <-- half-way at 22 moves. (Symmetrical board, not actually half-solved.)
12-b, 4-B, A-3, a-6-C-8, 3-A, B-4-6, b-5-B, 6-12-b, A-6-a-11, 8-C-6-A, 11-a, 1-C, 9-c

Both Alexander (the puzzle's poser), and Strasser Helmut sent identical computer solutions (below, they differ only in labeling). Alexander's summary is:

B-4,  D-2,  d-7,  A-3-10,  b-12,  7-b,  10-d,  4-B,  C-1-10,  c-6-C,
2-9-c,  a-11-2-D,  B-4-11-a,  b-5-B-4,  D-2,  d-7,  10-d,  12-3-A,  7-b,
4-B,  2-D

Strasser's move-by-move summary is:

  A,B ... white, black knights
  +   ... start point of move
  a,b ... target point of move


 1  + . . . A     9  . + . A .    17  . . . . B    25  + . . . B
    B . . . A        . . . . A        A . . . b        A . . . B
    B b . . A        b B . B A        B . . B A        . a . B .
    B . . . A        . B . . A        A . . + A        A . A . B

 2  . b . . A    10  . . . A .    18  . . . . B    26  . . . . B
    B . . . A        . . . . +        A . . a B        A . . . B
    + B . . A        B B a B A        B . . B A        a A . B .
    B . . . A        . B . . A        A . . . +        A . + . B

 3  . B . . +    11  . . . A .    19  . . . . B    27  . a . . B
    B . a . A        . . . . .        A . . + B        A . . . B
    . B . . A        B + A B A        B a . B A        + A . B .
    B . . . A        . B . b A        A . . . .        A . . . B

 4  . B . . .    12  . . . A .    20  . b . . B    28  . A . . +
    B b A . A        . . . . .        A . . . B        A . b . B
    . B . . A        B . + B A        + A . B A        . A . B .
    + . . . A        a B . B A        A . . . .        A . . . B

 5  . B . . .    13  . . . A b    21  a B . . B    29  . A . . .
    B + A . A        . . . . .        A . . . B        A . + . B
    . B . b A        B . . + A        . + . B A        . A . B b
    . . . . A        A B . B A        A . . . .        A . . . B

 6  . B . a .    14  . . . A B    22  A + . . B    30  . + . . .
    B . A . A        . . . . .        A . . b B        A . . . B
    . B . B +        B . . b A        . . . B A        a A . B B
    . . . . A        A + . B A        A . . . .        A . . . B

 7  . B . A .    15  . . . + B    23  A . . . B    31  . . . . b
    B . + . A        . . . . .        A . . + B        A . . . B
    . B . B a        B . a B A        . . . B A        A A . + B
    . . . . A        A . . B A        A . . . b        A . . . B

 8  . B . A .    16  . . . . B    24  A . . . B    32  a . . . B
    + . . . A        a . . . .        A . . . B        A . . . B
    . B . B A        B . + B A        . . . B +        A + . . B
    . b . . A        A . . B A        A . a . B        A . . . B

UPDATE 9/20/2004: Richard Mathar found the following 32-move solution to the same problem with Knights:

32 moves:
0:
|WK|  |  |  |BK|
|WK|  |  |  |BK|
|WK|  |  |  |BK|
|WK|  |  |  |BK|

1:
|  |  |  |  |BK|
|WK|  |  |  |BK|
|WK|WK|  |  |BK|
|WK|  |  |  |BK|

2:
|  |  |  |  |BK|
|  |  |  |  |BK|
|WK|WK|  |  |BK|
|WK|WK|  |  |BK|

3:
|  |  |  |  |BK|
|  |WK|  |  |BK|
|WK|WK|  |  |BK|
|  |WK|  |  |BK|

4:
|  |  |  |  |BK|
|  |WK|  |  |  |
|WK|WK|BK|  |BK|
|  |WK|  |  |BK|

5:
|  |  |  |  |BK|
|  |WK|  |  |  |
|WK|  |BK|  |BK|
|  |WK|  |WK|BK|

6:
|  |  |  |  |BK|
|  |WK|  |BK|  |
|WK|  |BK|  |BK|
|  |WK|  |WK|  |

7:
|  |  |  |  |BK|
|  |WK|  |BK|  |
|WK|  |  |  |BK|
|  |WK|  |WK|BK|

8:
|  |  |  |  |BK|
|  |  |  |BK|  |
|WK|  |  |  |BK|
|WK|WK|  |WK|BK|

9:
|  |  |  |  |BK|
|WK|  |  |BK|  |
|WK|  |  |  |BK|
|WK|  |  |WK|BK|

10:
|  |  |WK|  |BK|
|  |  |  |BK|  |
|WK|  |  |  |BK|
|WK|  |  |WK|BK|

11:
|  |  |  |  |BK|
|  |  |  |BK|WK|
|WK|  |  |  |BK|
|WK|  |  |WK|BK|

12:
|  |  |  |  |  |
|  |  |  |BK|WK|
|WK|  |  |BK|BK|
|WK|  |  |WK|BK|

13:
|  |  |  |  |  |
|  |  |  |BK|WK|
|WK|  |  |  |BK|
|WK|BK|  |WK|BK|

14:
|  |  |  |  |  |
|  |WK|  |BK|WK|
|WK|  |  |  |BK|
|  |BK|  |WK|BK|

15:
|  |  |  |  |  |
|BK|WK|  |BK|WK|
|WK|  |  |  |BK|
|  |  |  |WK|BK|

16:
|  |  |  |  |  |
|BK|  |  |BK|WK|
|WK|  |  |WK|BK|
|  |  |  |WK|BK|

17:
|  |  |  |BK|  |
|BK|  |  |BK|WK|
|WK|  |  |WK|  |
|  |  |  |WK|BK|

18:
|  |  |  |BK|  |
|BK|  |WK|BK|WK|
|  |  |  |WK|  |
|  |  |  |WK|BK|

19:
|  |BK|  |BK|  |
|BK|  |WK|  |WK|
|  |  |  |WK|  |
|  |  |  |WK|BK|

20:
|  |BK|  |BK|  |
|BK|  |WK|BK|WK|
|  |  |  |WK|  |
|  |  |  |WK|  |

21:
|  |BK|  |BK|WK|
|BK|  |WK|BK|WK|
|  |  |  |  |  |
|  |  |  |WK|  |

22:
|  |BK|  |  |WK|
|BK|BK|WK|BK|WK|
|  |  |  |  |  |
|  |  |  |WK|  |

23:
|  |BK|  |  |WK|
|BK|BK|  |BK|WK|
|  |  |  |  |WK|
|  |  |  |WK|  |

24:
|  |BK|  |  |WK|
|  |BK|  |BK|WK|
|  |  |  |  |WK|
|  |BK|  |WK|  |

25:
|  |  |  |  |WK|
|  |BK|  |BK|WK|
|BK|  |  |  |WK|
|  |BK|  |WK|  |

26:
|  |  |  |  |WK|
|  |BK|  |BK|  |
|BK|  |WK|  |WK|
|  |BK|  |WK|  |

27:
|  |  |  |  |WK|
|  |BK|  |BK|WK|
|BK|  |WK|  |WK|
|  |BK|  |  |  |

28:
|  |  |  |  |WK|
|  |BK|  |  |WK|
|BK|BK|WK|  |WK|
|  |BK|  |  |  |

29:
|  |  |  |  |WK|
|  |BK|  |  |WK|
|BK|BK|  |  |WK|
|  |BK|  |  |WK|

30:
|  |  |  |  |WK|
|  |  |  |  |WK|
|BK|BK|  |  |WK|
|BK|BK|  |  |WK|

31:
|  |  |  |  |WK|
|BK|  |  |  |WK|
|BK|BK|  |  |WK|
|BK|  |  |  |WK|

32:
|BK|  |  |  |WK|
|BK|  |  |  |WK|
|BK|  |  |  |WK|
|BK|  |  |  |WK|

Mail to Ken