12
$\begingroup$

Can you swap black and white knights in this 4x4 grid? There is one important constraint: at no point can a knight be under attack by an opponent knight. Knights move using standard chess moves (L shapes) and can be moved in any order (no need to alternate colours). Knights cannot exit the grid.

enter image description here

Improve this question
$\endgroup$

3 Answers 3

Reset to default
14
$\begingroup$

It is

possible. We can even alternate black and white. The following uses 11 moves (22 semi moves):

[FEN "nnn5/8/8/NNN5/8/8/8/5k1K w - - 0 1"] 1.Ncb7 Ncb6 2.N5d6 N8d7 3.Nd8 Nd5 4.Nac6 Nac7 5.Nc8 Nc5 6.N6a7 N7a6 7.Ndc6 Ndc7 8.Nb6 Nb7 9.Nac8 Nac5 10.Nb8 Nb5 11.Na8 Na5 *

enter image description here

Replay

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very nice and well done! $\endgroup$
    – Dmitry Kamenetsky
    Commented Mar 29, 2021 at 0:07
  • $\begingroup$ This is much better. $\endgroup$
    – nonuser
    Commented Apr 4, 2021 at 15:41
8
$\begingroup$

loopy walt beat me to the punch while I was editing the image. Here it is anyway (with a different order of moves):

enter image description here

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Nice. Can you make it symmetric? Usually this kind of problem can be made symmetric. So the first 5 transitions will give 5 different configuration, then one transition to get the same configuration but mirrored, then the last 5 transitions will be simply the reverse of the first 5. $\endgroup$
    – justhalf
    Commented Mar 28, 2021 at 14:59
3
$\begingroup$

Not an answer, but I would like to share my initial approach, before I figured that it's as helpful as I thought it was going to be.

The idea for this kind of problem usually is to convert it into a graph, then usually its easier to visualize the solution. But not for this case, apparently.

In the graph below, each node represents a square, and the edges represent the possible knight moves between squares. Red nodes represent black, green nodes represent white. Following loopy walt's notation, I use the a5-d8 part of the chessboard. The problem is then to switch the red and green nodes by moving the color along the edges, with the requirement that at any time, no two different colors should be adjacent.

enter image description here

Here we can see that only b6 and b7 are free for the first move, which can come from a8/c8 and a5/c5. I thought there could be a single Hamiltonian cycle on this graph on which we can simply move the colors. But there is none that would preserve the requirement of no two different colors should ever be adjacent.

At first I was thinking of a8-b6-d7-c5-a6-b8-c6-a5-b7-d6-c8-a7-b5-c7-a8. But the d7-c5-a6-b8 part won't be tenable to moving two different colors, due to the edge between d7-b8.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ I think looking at this graph does give us a good way to find a solution. After c5-b7, a8-b6, b7-d8, b8-d7, there's nothing stopping green from making the moves a5-c6 and b5-a7 while red does something time-wasting like b6-d5-b6. At this point, green's pieces are n the top right of the graph (a7, c6, d8) while red's pieces are in the bottom left (a8,b6,d7). We can then move both sets of pieces around the external cycle a8-b6-d7-c5-b7-d8-c6-a7-b5-c7-a8 until they swap places, and finally, reverse the initial set of moves. This is not optimal, but it does get us there. $\endgroup$
    – Misha Lavrov
    Commented Mar 28, 2021 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.