6
$\begingroup$

Some examples: Desegregate the Knights and Switch The Knights

You must give two 8x8 chess board positions that have any number of black and white knights.

  • Both boards must have the same number of each colour of knights.
  • It must not be possible to arrive at the second board position from the first (and vice versa) using a finite number of L-shaped chess knight moves, that do not necessarily have to be played one colour at a time. (2 or more moves of the same coloured knights can be played in succession)
  • All knights of the same colour are indistinguishable and all knights of different colours are.

What is the minimum number of knights required to do so?

$\endgroup$
  • $\begingroup$ P.S. math or graph-theory may also be valid here, but I had already run out of tags. $\endgroup$ – ghosts_in_the_code Jan 14 '16 at 18:24
  • $\begingroup$ I'm a little confused by your second bullet point; are you saying just that moves do not have to alternate between white and black, or are you saying that more than one knight may move at once? $\endgroup$ – 2012rcampion Jan 14 '16 at 18:31
10
$\begingroup$

All 64 knights are needed, in which case any setup is stuck. We prove that with 63 knights, any position is reachable from any other position.

With 63 knights, the puzzle is much like a sliding puzzle, except pieces slide as knight moves rather than into orthogonality adjacent cells. We can think of a move as swapping the position of the hole and the knight that moves into it.

Rather than having the knights be colored, let them be labelled 1 through 63, similar to the 15 puzzle. As the 15 puzzle, there is an invariant that means only half the positions are reachable: the parity of the permutation (labelling the hole as "64") plus the color of the hole square. Each move swaps the hole with a knight, switching both the parity of the permutation and the color of the hole square, preserving the invariant.

We'll argue that, like for the 15 puzzles, one can reach any position with with the same invariant. First, move the hole to the right spot, then we show that any even permutation can be obtained while keeping the hole where it is.

With three knights and a hole X in a four-cycle, one can have the hole do a lap clockwise to rotate the knights along a three cycle.

    2          3
1          2      
      3          1    
  X          X    

With knights 1,2,3 in this formation anywhere on the board, we can always move the hole X to the right place via other spaces to catalyze their rotation, then move the hole back the way it came, so the board is as it started except for those three knights.

One can do the same along other 3-cycle formations

    2
1       3
    X

1
    3
  2
      X

In fact, this lets us rotate any three knights in a path of three that isn't a straight line. Using a knight's tour graph with no straight lines, we can cycle any three adjacent cells in the tour.

enter image description here

Finally, permutations of three adjacent elements suffices to generate all even permutations, as shown in theorem 3.4 here.

It only remains to show that the invariant doesn't prevent correctly colored knights in the original problem. Since there's either at least two white knights or two black knights, we can always swap their labels to reverse the invariant.

$\endgroup$
  • 1
    $\begingroup$ I think the gist of it is: the existence of a knight's tour means we can move the position of the hole in the cycle. This does not suffice, because it preserves the order of knights in the cycle of the tour. However, the existence of the small 4-cycles allow us to change that order in the knight's tour. $\endgroup$ – Fimpellizieri Jan 15 '16 at 4:18
1
$\begingroup$

I believe the answer is

64 knights

because

a knight on any square can reach any square on a 8x8 board in a finite number of moves. If you try to block a knight from moving by placing knights in each square it can move to, you must then block the new knights again and again until no knight can move. This inevitably results in the entire board being filled.

Al alternate way to prove this (which I don't have the patience for) would be to prove

that it is possible to swap 63 knights from even one starting position.

$\endgroup$
  • $\begingroup$ I am not convinced for only 1 reason: It does not prove there cannot be a loop simular to that in Desegregate the Knights. If that is possible, however, the result is probably 63 knights. $\endgroup$ – kaine Jan 14 '16 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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