Website founded by
Milan Velimirović
in 2006
1:03 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 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 :-)
| | | (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,n-S 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,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.
| |
No more posts |
MatPlus.Net Forum General Very nonattacking rooks |
|
|
|
ISC 2024
