Twelve Knights

[arif]

You must be familiar with the eight queens problem, where you have to place eight queens on a board so that no queen can capture another.

If we place knights in the following formation

n n - - n n - -
n n - - n n - -
- - - - - - - -
- - - - - - - -
n n - - n n - -
n n - - n n - -
- - - - - - - -
- - - - - - - -

We have twelve knights such that none can capture any other.

What is the maximum number of knights that can be placed on the chessboard with the same conditions.

[Very easy once you see the answer]

[stijn263]

32 ?

[jaap]

We have twelve knights such that none can capture any other.

I think you'll find your example has 16 knights.

[uws8505]

I get it. If we fill the dark squares on the chessboard(as you know) with knights, there are no knights capturing each other.

[Eigenray]

For an mxn board, that gives a lower bound of mn/2 or (mn+1)/2. If there exists a knight's tour, we get an upper bound of mn/2. But if not?

[uws8505]

If there exists a knight's tour, we get an upper bound of mn/2.

A knight's tour may exist on a board with odd number of cells(such as 5*5). Then the upper bound should be (mn+1)/2, not mn/2.

[jaap]

If there exists a knight's tour, we get an upper bound of mn/2.

A knight's tour may exist on a board with odd number of cells(such as 5*5). Then the upper bound should be (mn+1)/2, not mn/2.

Yes. Maybe Eigenray was thinking only of closed knight's tours.

Long, complete, and I hope correct analysis follows:

Expand

According to wikipedia, they exist on all boards except for 1xn, 2xn, 4xn, 3x6, 3x8 and mxn with m,n both odd.

As you rightly point out, if you have an open knight's tour on any of those remaining boards, the upper bound is also (mn+1)/2 or mn/2, whichever is an integer.

In fact, you don't need a single tour at all. You can use any number of disjoint paths that together form the whole board. Each path of length L contributes L/2 or (L+1)/2 to the upper bound, whichever is an integer.
In particular, paths of length 2 are quite handy. This easily shows that 4xn with even n has upper bound 2n.

For mxn, with m,n odd, you can reduce it to an (m-4)x(n-4) rectangle by putting closed loops around the board in the two outer rows/columns. This eventually reduces the problem to one with a closed tour (incl. 1x1), or a 3x3 board. The 3x3 can be reduced to the 1x1 case by a loop visiting all 8 outer squares.

This leaves 1xn, 2xn, 4xn (n odd), 3x6, 3x8.

1xn can be completely filled. There are no non-trivial paths.
2xn. The knight graph decomposes into 4 paths.
- On 2x4k boards these are all of even length 2k so we have a tight bound of 4k.
- On 2x(4k+2) boards they are all of odd length 2k+1, and so it is possible to place 4k+4 knights. Simply alternate 2x2 blocks of knights with 2x2 empty blocks.
- The 2x(4k+3) board is simply the 2x(4k+2) case with one extra column, and it can also hold 4k+4 knights.
- The 2x(4k+1) board is simply the 2x(4k+2) case with one less column, so it can hold 4k+2 knights.

3x4: Can be decomposed into 2 loops of length 6, and can hold at most 6 knights.
3x6: Can be decomposed into 4 paths of length 4. Therefore can hold at most 9 knights.
3x8: Considered as two 3x4, it can hold at most 12 knights.

4xn, n odd: 4x3 is a 3x4. Larger ones can be dealt with like the m,n odd case. Loops can be made that follow the outer two rows/columns around the board. On this type of board there will be two loops, of the same even length, and so this board also has upper bound mn/2 = 2n.

Conclusion:
An mxn board can contain at most mn/2 or (mn+1)/2 non-attacking knights, except for:
- 1xn, n knights.
- 2x(4k+2), 4k+4 knights.
- 2x(4k+3), 4k+4 knights.
- 2x(4k+1), 4k+2 knights.

[uws8505]

That's an interesting result

[jaap]

There was a slight oversight in my analysis, though the result stays the same.

Expand

What I missed in my previous post was that reducing the m,n odd case as I did can also lead to 3xk or 5xk rectangles. I was only thinking of odd squares when I wrote that up. It can be easily fixed, but I now prefer a slightly different proof.

I can be proved without relying on Schwenk's theorem about closed knights tours, by using the following steps:

1. Prove the special cases 2x4, 3x4, 3x6, 5x6 hold at most A/2 knights, where A=area.
2. Prove the special cases 3x5, 3x3, 5x5 hold at most (A+1)/2 knights.
3. Prove that any mxn board with m,n>2 can be dissected into the rectangles from (1) above, together with at most one rectangle from (2).
4. Show that therefore any mxn board with m,n>2 therefore has at most A/2 or (A+1)/2 non-attacking knights.

The 1xn and 2xn boards still have to be done separately as before.

[Maddox]

Hey interesting result. I like that type of game which belong with math. I will play this game in this Sunday then i will post my result on it.