Answer to
old chestnut: four chess knights:
The solutions to both problems are easier if you notice that there are just two spaces that a knight can reach from any space on the board, and the squares on the edge are connected this way into one long cyclic path. (The center is unreachable.)
If the board looks like:
3 N.n
2 ...
1 N.n
abc
then the path looks like a3-b1-c3-a2-c1-b3-a1-c2-(a3), and the knights are in
alternate squares.
Since no two knights can occupy the same square (or we wouldn't have four knights left at the end to occupy the starting squares), all the knights must move in the same direction around this modified path.
Thus, the knight on a3 must end up on c1, a1 must end up on c3, and vice versa.
Thus, each knight must move four times, for 16 moves total.
When consecutive moves by the same knight count as only one move, clearly the best you can do is one move on the first move (by any knight). Then two on the second, by the knight who was "behind" that one on the path, three by the next, and four by the last. Then each knight (except for the one who moved last) can move once more to reach his destination. Total: 7 moves.
Moves in full (other solutions possible by rotation and reflection):
N a3-b1
N a1-c2-a3
n c1-b3-a1-c2
n c3-a2-c1-b3-a1
N b1-c3-a2-c1
N a3-b1-c3
n c2-a3