MatPlus.Net

 Website founded by
Milan Velimirović
in 2006

8:50 UTC
ISC 2020
 
  Forum*
 
 
 

Username:

Password:

Remember me

 
Forgot your
password?
Click here!
SIGN IN
to create your account if you don't already have one.
CHESS
SOLVING

Tournaments
Rating lists
1-Oct-2020

B P C F





 
 
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