You can get famous (OK, Warhol-15 minutes-famous :-)!
First a few definitions. Of course, two rooks of the same colors don't attack, but since two colors are needed, "attacking" here means "attacking or protecting".
- The "rectangle of two rooks" is the smallest rectangle along the board lines containing both. E.g. Ra1+Re3: all fields with file a,b,c,d,e AND rank 1,2,3.
- A rectangle is "empty" if it contains only the two rooks AND they are nonattacking. E.g. Ra1+Rb2: if a2 and b1 are empty, it is empty. (Opposite "full")
- A position is "empty" if at least one rectangle of two rooks is empty. (Opposite "full") E.g. Ra1,Ra2,Rb2 is full. (a2 attacks both, a1+b2 contains a2.)
- You start with a self-chosen empty position consisting of n nonattacking black rooks on a nxn board.
- Goal: Add as few white rooks as you can such that the position is full.
Now there is a famous algorithm from binary search trees, "Geometric Greedy Future" (GG), which is very hard to beat.
- Outer loop: Scan through all ranks, starting at the lowest rank and working upward.
- Inner loop: Scan outwards, file by file in each direction, from the black rook in the current rank. If a rook in file X and a lower rank forms an empty rectangle with a rook in the current rank, fill it by placing a white rook on the current rank, also on file X. Here is an image: Color coding:
- Green line: Current rank
- Black dots: Black rooks
- Blue marks: Rooks forming an empty rectangle with a rook on the current rank
- Orange marks: Places white rooks should be
- Red dots: White rooks
- Green marks: Places white rooks don't need to be, since their rectangle is already full
Notice that the algorithm places six rooks in the above example, whereas the diagram on the right (among others) fills the position using five.
You can have endless fun (for fuzzy values on fun - but after all I wrote my whole master thesis on it :-) with this game (choose a random position, find the optimum), but I have a concrete question. As shown above, GG can be beaten, and it can be beaten hard (I managed 26/17 as a limiting ratio between GG's output and optimal placement, mail me if you can do better!). This is because I placed the black rooks in a way that causes GG to place lots of unnecessary white rooks, as shown in the position below:
- Green lines show rectangles considered by the algorithms. Consider the diagrams as graphs, with these as edges.
- Blue, black, and grey boxes are black rooks touching one, two, and three edges, respectively.
- Orange, red, and yellow-marked boxes are white rooks touching two, three, or four edges, respectively.
The GG algorithm places a total of 104 rooks (left), whereas at most 73 are needed to fill the position (right): a wastage of approximately 42.5%.
Look at the expensive pattern in the middle: A zig-zag strip of width 4 that adds two white rooks in every row, in addition to the rooks placed in the left and right halves.
Is it possible for the GG algorithm to produce a zig-zag strip of width 5? (You can ask me for a working Python program so you just have to enter the starting position.) In particular,
is it possible to arrange rooks such that white rooks are placed in the red spaces below and not the green one?
(Look at the preceding picture to see how this works with strip width 4. If you have an impossibility proof, please mail me too.)