Geometric game on a n*n chessboard

Question

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:
Color coding:

• 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.)

Answer 1

I might have something here.
Since the rectangle-seeking phase only looks downwards, the first zigzag cell in any file must be a black rook. Without loss of generality, then, consider this example setup, where yellow cells are black rooks and white cells are white rooks:

I wish to block white rooks from being placed in the red cells. The width-4 zigzag could be made because only the rightmost red cell would need to be blocked, and it can be blocked like so - the blue cell is free to remain vacant on account of the green square:

However, the black rook in the rank above the green cell must be to the left of the zigzag in order for the zigzag to continue leftward, which means that the zigzag will block any rectangles that could reach the right half of the board. This means that no "green cells" can appear in that rank, and the left red cell cannot remain unfilled.

Of course, if you allow multiple black rooks to occupy the same file, then you can have zigzags of any desired size and shape. This construction, however, is rather trivial: