﻿﻿ MatPlus.Net

Website founded by
Milan Velimirović
in 2006

8:50 UTC
 ISC 2020

Remember me

 CHESS SOLVINGTournamentsRating lists1-Oct-2020
 B P C F

MatPlus.Net Forum General Very nonattacking rooks

### Very nonattacking rooks

This came up en passant in my computer science Master thesis,
but you don't write it for me if you solve it :-)

(= 8+0 )

"Very" as in "the closest distance is knight". (Also, since
I like symmetry, this is the parallel projection of a cube.)
So, think of nonattacking (R+S). Maybe this already was done.
Can you improve on "knight"? If not, can you do it on a larger
chessboard? (Better hurry up, since I can write a FORTRAN
program faster than it gives the solution :-)

Here we have already Alfil distance. Doubt that more is possible...

(= 8+0 )

Here the Rh8 has a bit more distance - is that the maximum possible?

(= 8+0 )

Yours is a two-vector construction, which can be easily
generalized to a n*n board. If n=m^2, it should be
optimal in any case. (9*9 already allows camel distance.)

Incidentally, you also proved that maximum distancing
is good against Corona, but not for the problem I am
researching :-) (Quick non-description - it is far more
complicated: Count 1\$ for any pair of rooks which rectangle
doesn't enclose another rook. Your solution earns 15\$,
if I counted right, but mine 20\$. And if you now place
the rooks on e1-h4 and a5-d8, there are complicated
reasons why this doesn't count as 22, but only 13\$.
Hopefully, my thesis comes out at my 60th birthday :-)

Okay... Did not understand how you counted that but maybe then this here has some dollars more? If so, I will send you my bank account details!

(= 8+0 )

Also 20\$ (for *that* I have a program, for n=8 this
is maximal). It is also another n=8 example (I already
found one) for the worst efficiency of a certain algorithm.

I have a proof that for any position with 8 nonattacking rooks, there are 2 rooks in a distance of Sqrt[8] or less.

Suppose there is a position with a minimum distance of Sqrt[10] or greater. Any rook placed in one of the 16 central squares blocks a 5x5 square around itself. Consider this example of a rook at d5 (black pawn means the square is blocked):

(= 1+24 )

We need to place four more rooks in columns b, c, e, f, however they can be placed in three rows 1, 2, 8 only, which is impossible. Therefore the position we are looking for cannot contain a rook at d5, or analogously at one of the other 15 central squares.

Now consider the remaining squares:

(= 0+16 )

The rooks can be placed on rows 1, 2, 7, 8 and columns a, b, g, h. We have eight rows or columns for eight rooks, therefore we cannot afford to "waste" any of those - any rook that uses two of those doesn't leave enough room for the others. This means we cannot place a rook at a1, b1, a2 or b2, same for the other corners:

(= 0+32 )

Each of the remaining 4x2 rectangles can hold two rooks, but they are obviously not compatible with each other; therefore no such position exists.

Please note that this proof only works for 8x8 boards. In 9x9, there is a symmetric solution: a7, b4, c1, d8, e5, f2, g9, h6, i3, which can be easily extended for larger boards (add j10 for a 10x10 board etc). I'm pretty sure that Sqrt[10] is the minimum distance for 9x9 boards, larger boards will have larger minimum distances.

I'm rather convinced that for any board of size n^2,
the rotated grid with 1,n-S distance is optimal, and
this value is maximal until the (n+1)^2 board.

Isn't the 2,2-distance for an 8x8 board a counterexample for this?

(10) Posted by Hauke Reddmann [Thursday, Nov 19, 2020 09:45]

Did I formulate it wrong? I mean "maximum minimal". I try again:
4*4 board - normal S - all boards until 9*9 have at
least 2 R that are in S distance.
9*9 - C - and so on.