## Twelve Knights

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

### Twelve Knights

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
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

### Re: Twelve Knights

32 ?
jaap
Posts: 557
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Twelve Knights

arif wrote:We have twelve knights such that none can capture any other.
I think you'll find your example has 16 knights.
uws8505
Posts: 58
Joined: Tue Sep 30, 2008 3:13 pm
Location: South Korea

### Re: Twelve Knights

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 5:20 pm

### Re: Twelve Knights

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
Posts: 58
Joined: Tue Sep 30, 2008 3:13 pm
Location: South Korea

### Re: Twelve Knights

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
jaap
Posts: 557
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Twelve Knights

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
uws8505
Posts: 58
Joined: Tue Sep 30, 2008 3:13 pm
Location: South Korea

### Re: Twelve Knights

That's an interesting result
Math and Programming are complements
jaap
Posts: 557
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Twelve Knights

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