4 Knights

In the early part of How to solve it : Modern Huristics there is a simple looking problem where by four chess knights have to swap position on a four by four chess board.

Going from this ..

To this ...

Just using the Knight's Y shaped move (1 othogonal move N,S,E,W followed by + 1 diagonal move NE,NW,SW,SE in the shape of a partial Y) for each piece with no overlapping or off edge pieces.

Starting by numbering the squares, it can be seen that square 5 cannot be reached by any of the knights leaving just the outer squares to be used. 

Rather than just puersuing a random, move by move search, a strategy should be devised. It can be noticed that, from the start, any of the pieces can be moved at least once and if all the pieces move then no subsequent move is blocked.  Also consider that any single piece can "tour" all the available squares and without revisting any square, return to it's starting place.  This tour is the route we are after. If each piece is moved one step at a time along the tour route then progress can be stopped when the pieces are in the desired end position.

Discovering the tour.

The tour order includes each square [ 1,2,3,4,6,7,8,9 ] once only.  All the possible tour routes can be generated using simple permutation then filtering invlaid route. As the route will start at square 1 that does not need to be permutated.

Permute [ 2,3,4,6,7,8,9 ] generates 7! = 5043 lines 

2 3 4 6 7 8 9

2 3 4 6 7 9 8

2 3 4 6 8 7 9

2 3 4 6 8 9 7

....

9 8 7 6 3 2 4

9 8 7 6 3 4 2

9 8 7 6 4 2 3

9 8 7 6 4 3 2

but many of these lines contain invalid moves. Because the tour we seek starts at 1 every valid line must have either 6 or 8 as the next move. Lines starting with 6 must end with 8 (and visa versa) to ensure that square 1 is the start and finish of the tour.  Also each pair of numbers within the line must be a valid knights move.

The valid knight's moves are :

1 6

1 8

2 7

2 9

3 4

3 8

4 3

4 9

6 1

6 7

7 2

7 6

8 1

8 3

9 2

9 4

once all the lines that contain other number parings are removed we are left with two tours. On exmaination we see one is a clockwise and the other anti-clockwise.

Tour Routes are 

1 6 7 2 9 4 3 8

1 8 3 4 9 2 7 6

and finally each pieces step by step move is revealed along with some checks.

Read cols vertically to check that only one piece is in a place at each turn.

There should be no repeated numbers between sucessive columns to ensure each piece is moving to an empty square.

Piece 1 -> 1 6 7 2 9 

Piece 3 -> 3 8 1 6 7 

Piece 7 -> 7 2 9 4 3 

Piece 9 -> 9 4 3 8 1 

Done

In conclusion

This puzzle is a classic case that required reframing in order to make progress. Modling moving of four pieces at once would have been awkward but simplfying to "move a single piece all round the board" and then have each other piece follow in footsteps greatly improved the focus for finding the solution.