8
$\begingroup$

In From knights to kings, we were asked

On a NxN chess board $N^2$ knights are placed (one per cell). Each pair of knights, who control each other (i.e. one move away from each other) are friends. One day all knights are promoted to kings. Is it possible to put them on the board (in different order) that all friends will be similarly one move away from each other?

We found out that for a square board, we can't put all the knights next to their friends when $N>3$. What if we are using a $N\times M$ board ($N\ge M$) instead? For example, if $N=3,M=2$:

A B C
D E F

You only need to swap D and F to get a solution

A B C
F E D

It's fairly obvious that all $N\times 1$ and $N\times 2$ boards will work. What other board sizes will work under these conditions?

$\endgroup$
  • $\begingroup$ Are they allowed to be 1 move away from someone they aren't friends with? $\endgroup$ – kaine Oct 31 '14 at 16:49
  • $\begingroup$ @kaine Yes. As long as a piece is next to all of its friends, it doesn't care what other pieces it is next to. $\endgroup$ – Rob Watts Oct 31 '14 at 18:24
5
$\begingroup$

Assuming "castle" maneuvers are not a part of this drill: Also, symmetry is not drawn out; you can always flip these boards around.

Anything 4x4 and larger doesn't have a valid solution. A 4x4 board will generate knights with 4 friends. You can't place 5 friendly kings on a board where each is one move away from the other 4 (neglecting "castle" maneuvers!). That was incorrect reasoning. The "friendliness" is not contagious.

Anything 6x7 and larger definitely doesn't have a valid solution. This size board will result in knights with 8 friends, some of whom have 6 or more non-mutual friends. You can't arrange these 2 such that the first has access to all 8 and the second has access to 6 or more additional friends.

Square 6x6 not allowed.

Can't do 5x6 or larger. You'll end up with two knights that have 8 friends, 0 mutual friends. x has friends a-h, X has friends A-H:

. a . b .
c A . B d
C . x . D
e . X . f
E g . h F
. G . H .

They must go here on the King Board:

. . 0 0 0   . 0 0 0 .   0 0 0 . .
. . 0 x 0   . 0 x 0 .   0 x 0 . .
. . 0 0 0   . 0 0 0 .   0 0 0 . .
0 0 0 . .   . 0 0 0 .   0 0 0 . .
0 X 0 . .   . 0 X 0 .   0 X 0 . .
0 0 0 . .   . 0 0 0 .   0 0 0 . .

Each of the friends of x and X (meaning a-h and A-H) have at least 2 non-mutual friends with the x's. This means none of them can go on the corners of the King Board, since they won't have access to anyone else, nor can they be boxed-in on an edge, so we can't solve this one.

Square 5x5 is not allowed.

Nor can you do 5x4:

a b c d
e f g h
i j k l
m n o p
q r s t

j and k each have 6 friends. Each of j's friends have at least 1 friend that isn't mutual with j (same goes for k). Also, since j and k have 0 friends in common, they must be diagonal from each other. These are the only places on the King Board where j and k could go and have access to 6 friends each. All of them puts one of their friends in a spot where they can't reach all of their own friends:

. . . .   . . . .   . . . .
. . j .   . . j .   . . j .
. k . .   . . . .   . . . .
. . . .   . k . .   . . k .
. . . .   . . . .   . . . .

Square 4x4 is not allowed.

3x4 is the largest that's good to go I've solved explicitly so far:

1  2  3  
4  5  6  
7  8  9  
10 11 12  

which means (knight: friends)

1: 6,8  
2: 7,9  
3: 4,8  
4: 3,9,11  
5: 10,12  
6: 1,7,11  
7: 2,6,12  
8: 1,3  
9: 2,4,10  
10: 5,9  
11: 4,6  
12: 5,7  

and valid solution:

3  8  1  
4  11 6  
9  2  7  
10 5 12  
$\endgroup$
  • $\begingroup$ I don't understand your argument making 4x4 impossible. A knight can have 4 friends but the 4 friends aren't friends. So they don't need to be neighbours to each other. $\endgroup$ – Florian F Oct 31 '14 at 20:42
  • $\begingroup$ @FlorianF You're totally right. My original understanding of the question involved "friend groups", and I never discarded this conclusion after I updated my understanding of friendliness! I'll remove that comment. $\endgroup$ – anregen Oct 31 '14 at 20:46
4
$\begingroup$

For a 3x3 board we can do

A B C      A H C
D E F  ->  F E D
G H I      G B I

For a 3x4 board we can do

A B C D      A J C L
E F G H  ->  G H E F
I J K L      I B K D

I can't find others.

$\endgroup$
  • $\begingroup$ ... and it's exactly the same solution for 3x4 as anregen's. Maybe it's the only one? $\endgroup$ – Florian F Oct 31 '14 at 20:35
  • 1
    $\begingroup$ can you change the 3x3? there are 2 D's in the solved part but it's too small of an edit for me to do. $\endgroup$ – mdc32 Oct 31 '14 at 20:53
  • $\begingroup$ Thanks. Fixed. It was a test to see if you are paying attention. :-) $\endgroup$ – Florian F Oct 31 '14 at 22:09
3
$\begingroup$

I realize the 4x4 case has already been shown to not work, but let me try explaining it a bit differently -- a bit more "locally". Consider a large board, and we'll only look at the 4x4 corner of it.

In an actual 4x4 board, by symmetry there are only three kinds of pieces, a corner piece (like $A$), and edge piece (like $B$), and a 'central' piece (like $C$).

$$\begin{matrix} A & B & . & c \\ c & . & a & b \\ b & a & C & . \\ c & .& . & . \end{matrix}$$

In a larger board there may be more room initially (and thus more friends to place), which gives more space/options to place pieces after promotion to kings, but I will show this extra room cannot help.

Now the corner piece $A$ has two friends $(a,a)$, the edge piece $B$ has three friends $(b,b,C)$ and the center piece $C$ has four friends $(c,c,c,B)$.

Regardless of how we rearrange the board, some piece needs to go in the corner.

Can $A$,$B$, or $C$ be placed in the corner after promotion to kings?

  • As a king in the corner only has room for three friends, it is clear a central piece like $C$ cannot be put there.

  • If we put $B$ in the corner, we have two edge friends $(b,b)$ and one central friend $(C)$ to place. So this gives us only two symmetry distinct layouts to consider

    $$\begin{matrix} B & b & . \\ C & b & . \\ . & . & . \end{matrix} \quad\quad or \quad\quad \begin{matrix} B & b & . \\ b & C & . \\ . & . & . \end{matrix} $$

    The first doesn't leave enough room for the three other friends of $C$, so can be eliminated.

    The second, there is no way to place the three other friends of $C$ without reducing at least one $b$ to only having room for one more friend.

    $$\begin{matrix} B & b & c \\ b & C & c \\ . & . & c \end{matrix} \quad\quad , \quad\quad \begin{matrix} B & b & . \\ b & C & c \\ . & c & c \end{matrix} $$

    Therefore there isn't room for the friends of the $b$ pieces, and this layout will not work.

    So an edge piece like $B$ cannot be placed in the corner after promotion to king.

  • That leaves $A$. Can a corner piece be placed in the corner after promotion?

    Well, if we put $A$ in the corner, this constrains placement of many pieces. Let me rename the starting positions to make the discussion more clear:

    $$\begin{matrix} A & f & \bar{e} & . \\ \bar{f} & . & \bar{a} & e \\ e & a & . & \bar{f} \\ . & \bar{e} & f & k \end{matrix}$$

    The overbars are used to allow making it clear two positions (such as $a$ and $\bar{a}$) are symmetry equivalent, even if we need to refer to them as separate pieces in the discussion.

    $A$ has friends $(a,\bar{a})$, the $a,\bar{a}$ each have two distinct $(e,\bar{e})$ and two common $(A,k)$ friends, the two $e$ have two common friends $(f,f)$ and the $\bar{e}$ have two common friends $(\bar{f},\bar{f})$.

    If we put $A$ in the corner, this gives us only two symmetry distinct layouts to consider

    $$\begin{matrix} A & \bar{a} & . \\ a & . & . \\ . & . & . \end{matrix} \quad\quad or \quad\quad \begin{matrix} A & \bar{a} & . \\ . & a & . \\ . & . & . \end{matrix} $$

    Looking at the first, forces placement of quite a few pieces

    $$\begin{matrix} A & \bar{a} & . & . \\ a & . & . & . \\ . & . & . & . \\ . & . & . & . \end{matrix} \quad\quad \rightarrow \quad\quad \begin{matrix} A & \bar{a} & \bar{e} & . \\ a & k & e & . \\ \bar{e} & e & . & . \\ . & . & . & . \end{matrix}$$

    While the bar's over the $e$ could be changed, it doesn't change the issue that there is no way to place the $(f,f)$ and $(\bar{f},\bar{f})$ so that they are common friends with the $e$ and $\bar{e}$ respectively. So this layout is not possible.

    The second layout offers more possibilities for where to place the $e,\bar{e}$ but the same problem arises. There is no way to place the $e$ pieces such that they can simultaneously be by their $a$ and $f$ friends.

  • So no piece can be placed in the corner. Thus 4x4 is not possible.


That was explained "locally" in the sense that having extra room on the board would not help matters. It should be clear that any board containing a 4x4 corner as a subset will not work.

As the question states 1xN and 2xN are not interesting, this then only leaves 3xN for N$\ge$3 to consider.

Let's first look at the 3x3 case.

$$\begin{matrix} a & d & g \\ f & x & b \\ c & h & e \end{matrix}$$

The friends can be written as cyclic graphs. $x$ stands alone, and $$ a \rightarrow b \rightarrow c \rightarrow d \rightarrow e \rightarrow f \rightarrow g \rightarrow h \rightarrow a$$

This is a completely "local" observation, in that any board having a 3x3 sub board in it will have this requirement. The unconstrained nature of $x$ along with the cyclic permutations for placement of $a...h$ gives quite a bit of freedom and many solutions for the 3x3 case.

A 3x4 board has two 3x3 sub-boards in it, and thus two cycles:

$$\begin{matrix} a & d,1 & g,4 & 7 \\ f & 6 & b & 2 \\ c & h,3 & e,8 & 5 \end{matrix}$$

There are no restrictions beyond the two cycles $a...h$ and $1...8$. So just shuffling to maintain the two cycles after promotion to kings gives

$$\begin{matrix} a & h,3 & g,4 & 5 \\ b & 2 & f & 6 \\ c & d,1 & e,8 & 7 \end{matrix}$$

There are of course other solutions, swapping $(f,6)$ or $(b,2)$ or $(2,f)$, or symmetry related solutions, etc. Note however that this is already constrained enough that once a corner for $a$ is chosen, all but the middle row is already fixed. These two cycles are so tightly interwoven that even if there was more room on the board, besides freedom in the middle row (or by symmetry rotating to a 4x3 solution), no additional solutions would be gained. So this is a local observation and can be applied to limit larger boards containing 3x4 subboards.

That proves by construction that the 3x3 and 3x4 case are possible. Now to finish this we can attempt to prove any board containing a 3x5 sub-board is not possible.

When we go to 3x5, we can either consider this three 3x3 sub-boards, or two 3x4 sub-boards. The 3x3 board has a lot of freedom (one piece was completely constrained) which turned out to have enough freedom to simultaneously solve the two 3x3 subboards in a 3x4 board. The resulting 3x4 solution still has some freedom, but is much more restrictive.

It turns out that it is not possible to simultaneously solve the two 3x4 subboards in a 3x5 board.

$$\begin{matrix} a & d,1 & g,4,A & 7,D & G\\ f & 6 & b,F & 2 & B\\ c & h,3 & e,8,C & 5,H & E \end{matrix}$$

There are no restrictions beyond the cycles $a...h$, $1...8$, and $A...H$.

Selecting $a$ to be in the same corner, the solutions from the 3x4 subboards gives the top and bottom rows as:

$$\begin{matrix} a & h,3 & g,4,A & 5,H & G \\ . & . & . & . & . \\ c & d,1 & e,8,C & 7,D & E \end{matrix}$$

There piece $b,F$ cannot simultaneously be by $a$ and $c$ and $G$ and $E$. So there is no solution.

One could also go back and prove the 4x4 board is not possible this way, by looking at it as two 3x4 subboards.

$\endgroup$

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.