Twelve Knights

Decision and strategy, simulations and probability models, card and board games, ...
Post Reply
User avatar
arif
Posts: 111
Joined: Tue Oct 09, 2007 3:35 am
Location: Lahore, Pakistan

Twelve Knights

Post by arif » Sun May 04, 2008 1:35 am

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]
The i-th root of i = 4.810477381

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 10:57 pm
Location: Netherlands

Re: Twelve Knights

Post by stijn263 » Sun May 04, 2008 8:27 am

32 ?

User avatar
jaap
Posts: 528
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Twelve Knights

Post by jaap » Sun May 04, 2008 1:40 pm

arif wrote:We have twelve knights such that none can capture any other.
I think you'll find your example has 16 knights.

User avatar
uws8505
Posts: 58
Joined: Tue Sep 30, 2008 2:13 pm
Location: South Korea

Re: Twelve Knights

Post by uws8505 » Wed Oct 01, 2008 4:11 am

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

Eigenray
Posts: 62
Joined: Mon Jul 14, 2008 4:20 pm

Re: Twelve Knights

Post by Eigenray » Wed Oct 01, 2008 11:12 am

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?

User avatar
uws8505
Posts: 58
Joined: Tue Sep 30, 2008 2:13 pm
Location: South Korea

Re: Twelve Knights

Post by uws8505 » Wed Oct 01, 2008 1:34 pm

Eigenray wrote: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.
Math and Programming are complements

User avatar
jaap
Posts: 528
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Twelve Knights

Post by jaap » Wed Oct 01, 2008 2:46 pm

uws8505 wrote:
Eigenray wrote: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.

User avatar
uws8505
Posts: 58
Joined: Tue Sep 30, 2008 2:13 pm
Location: South Korea

Re: Twelve Knights

Post by uws8505 » Mon Oct 06, 2008 11:18 am

That's an interesting result :D
Math and Programming are complements

User avatar
jaap
Posts: 528
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Twelve Knights

Post by jaap » Mon Oct 06, 2008 1:06 pm

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.

User avatar
Maddox
Posts: 1
Joined: Wed Aug 29, 2012 1:08 pm
Location: USA
Contact:

Re: Twelve Knights

Post by Maddox » Thu Oct 25, 2012 9:38 am

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.

Post Reply