Re: Challenge: Box Blackout (solved)

The best you can do is 2*N+1 holes. You can't achieve this for N < 5.

Otherwise, simply leave two (adjacent) edges empty (say left and bottom) and leave out two spots on a line adjacent to one of those edges (say second from bottom) where one of these two is on one diagonal and one isn't on either.

Update: Actually, "one diagonal" isn't specific enough. So, instead, leave the first row and the last column empty and leave blank the 2nd and 3rd spots on the second row.

The proofs involved aren't too complicated so I'll leave those for someone else to fill in. Update: Or not...

- tye

Comment on Re: Challenge: Box Blackout (solved)

Replies are listed 'Best First'.
Re^2: Challenge: Box Blackout (solved) by dragonchild (Archbishop) on Jan 24, 2006 at 15:52 UTC
Here's an another proof based on the idea of dependencies. A dependency is a square you cannot fill until you've filled one or more other squares. If you maximize the dependencies, you minimize the number of starting pieces. If you have an NxN grid, you can remove the top row and right column completely, removing (N + (N-1)) (or 2N-1) pieces. This will always work because you have N-1 pieces in every direction, thus allowing you to refill all them with no dependencies. You can have up to 1 dependent piece in the right column, so you can remove a piece not in a diagonal on the second row. This makes the second piece down in the right column dependent on all the other pieces. (This also locks in the 3rd and subsequent rows to being N-1.) This brings us up to N pieces removed. You can have up to 1 dependent piece in the upperleft/bottomright diagonal, so you can remove the piece in the second row correspdonding to that diagonal. (Remember, you cannot touch the 3rd and subsequent rows.) This brings us to 2N+1. This leaves 2 pieces that end up being dependent in the top row. But, since they were already removed, we can't count them. My criteria for good software: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply]

Replies are listed 'Best First'.

Re^2: Challenge: Box Blackout (solved)
by dragonchild (Archbishop) on Jan 24, 2006 at 15:52 UTC

If you have an NxN grid, you can remove the top row and right column completely, removing (N + (N-1)) (or 2N-1) pieces. This will always work because you have N-1 pieces in every direction, thus allowing you to refill all them with no dependencies.
You can have up to 1 dependent piece in the right column, so you can remove a piece not in a diagonal on the second row. This makes the second piece down in the right column dependent on all the other pieces. (This also locks in the 3rd and subsequent rows to being N-1.) This brings us up to N pieces removed.
You can have up to 1 dependent piece in the upperleft/bottomright diagonal, so you can remove the piece in the second row correspdonding to that diagonal. (Remember, you cannot touch the 3rd and subsequent rows.) This brings us to 2N+1.
This leaves 2 pieces that end up being dependent in the top row. But, since they were already removed, we can't count them.

My criteria for good software:

Does it work?
Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

[reply]