Website founded by Milan Velimirović in 2006
8:50 UTC
 
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 :)   (2) Posted by Arno Tungler [Tuesday, Nov 17, 2020 10:27]  Here we have already Alfil distance. Doubt that more is possible...
(= 8+0 )
  (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 )
  (4) Posted by Hauke Reddmann [Tuesday, Nov 17, 2020 11:15]  Yours is a twovector 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 nondescription  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 e1h4 and a5d8, there are complicated
reasons why this doesn't count as 22, but only 13$.
Hopefully, my thesis comes out at my 60th birthday :)   (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 )
  (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.   (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.   (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,nS distance is optimal, and
this value is maximal until the (n+1)^2 board.   (9) Posted by Ulrich Voigt [Thursday, Nov 19, 2020 00:22]  Isn't the 2,2distance 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.   No more posts 
MatPlus.Net Forum General Very nonattacking rooks 


