Website founded by
Milan Velimirović
in 2006

8:50 UTC
ISC 2020



Remember me

Forgot your
Click here!
to create your account if you don't already have one.

Rating lists


MatPlus.Net Forum General Very nonattacking rooks
You can only view this page!
(1) Posted by Hauke Reddmann [Tuesday, Nov 17, 2020 09:29]

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 :-)
(Read Only)pid=20005
(2) Posted by Arno Tungler [Tuesday, Nov 17, 2020 10:27]

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

(= 8+0 )

(Read Only)pid=20006
(3) Posted by Arno Tungler [Tuesday, Nov 17, 2020 10:54]

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

(= 8+0 )

(Read Only)pid=20007
(4) Posted by Hauke Reddmann [Tuesday, Nov 17, 2020 11:15]

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 :-)
(Read Only)pid=20008
(5) Posted by Arno Tungler [Tuesday, Nov 17, 2020 13:09]

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 )

(Read Only)pid=20010
(6) Posted by Hauke Reddmann [Tuesday, Nov 17, 2020 17:55]

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.
(Read Only)pid=20011
(7) Posted by Ulrich Voigt [Wednesday, Nov 18, 2020 11:26]

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.
(Read Only)pid=20013
(8) Posted by Hauke Reddmann [Wednesday, Nov 18, 2020 22:10]

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.
(Read Only)pid=20014
(9) Posted by Ulrich Voigt [Thursday, Nov 19, 2020 00:22]

Isn't the 2,2-distance for an 8x8 board a counterexample for this?
(Read Only)pid=20015
(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.
(Read Only)pid=20016

No more posts

MatPlus.Net Forum General Very nonattacking rooks