Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:
All,
Imagine that you have a N x N square and the object of the game is to black out the entire board in only 1 turn. The board starts out in an initial configuration with some pieces already on the board. Every time a row, column, or diagnol has N - 1 pieces in it you are allowed to place a piece in the empty position. Your turn is over when the board is blacked out or there are no more rows, columns, or diagnols that have N - 1 pieces in them.
Here is an example of a 3 x 3 grid
X|_|_ X|_|X X|X|X X|X|X X|X|X X|X|X X|X|X
_|X|_ -> _|X|_ -> _|X|_ -> X|X|_ -> X|X|X -> X|X|X -> X|X|X
X| | X| | X| | X| | X| | X|X| X|X|X
The object of the game is to find the optimal starting position for any size board where the number of starting pieces is minimized but the board can be covered in only 1 turn. While a 3 x 3 is trivial, I am really hoping to solve it for a 10 x 10.
I hope I have explained the idea well enough but if you have questions, please let me know. All solutions welcome to include brute force, golfed, and obfu.
Re: Challenge: Box Blackout (solved)
by tye (Sage) on Jan 24, 2006 at 00:43 UTC
|
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...
Indeed, you solve the problem backward. Start with a full N x N grid. You can remove one item if it is in a row, column, or diagonal that is still full. Remove as many items as possible.
Since there are N rows and N colums and 2 diagonals and removing a piece from any of them means they aren't full anymore, the most you could remove is 2N+2, one for each "full line". However, if you remove a piece that is in both a full row and a full column, then you've lost two "full line"s but only removed one item, reducing how many total items you could remove. So, to remove the most pieces, try to have each piece be in as few full lines as possible (but it must be in at least one or you aren't allowed to remove it).
But the first piece you remove will always be in both a full row and a full column and could also be in one or two full diagonals. So, the best solution would be to remove a first piece that isn't in any diagonal. Then remove each subsequent piece such that it is in only one full line. That is, each subsequent piece should come from a not-full row or column and shouldn't come from a diagonal unless it comes from both a non-full row and a non-full column. If you could do that, you would remove 2N+1 items.
So 2N+1 is the max. For N > 4, it is also easy to show that it is the min. The pattern I gave above shows how to construct a 2N+1 solution that works for any N > 4.
The pattern is easy to come up with. Remove the first item not on a diagonal (2nd item, 1st row). Then remove each remaining item from the 1st row that isn't on a diagonal (each will be in the non-full first row and in a full column) -- we are trying to make a very simple pattern that is easy to describe for any size of grid.
We need to get a non-full row and non-full column that intersect at an item on a diagonal. Remove the 3rd item on the second row to get this (this is the step that doesn't work for N < 5). So now you can remove the 2nd item on the 2nd row to take care of one diagonal. This makes it safe to remove the 1st item on the first row.
It'd be cool to remove the last item on the first row but it is on the other diagonal so we need to make the last column non-full first. So remove the last item on the second row. Now remove the last item on the first row. That takes care of both diagonals, all columns, and the first two rows.
Finally, remove the last item from the 3rd and subsequent rows. You've removed 2N+1 items so you can't do better than that.
| [reply] |
|
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] |
Re: Challenge: Box Blackout
by traveler (Parson) on Jan 24, 2006 at 00:09 UTC
|
Great game. My first thought at a solution would be a classic inverse backtrack: start with a full board and work backward.
Note that boards with just one piece missing are solutions (not optimal!) and so are all predecessors to a full board in a path such as you show. So, working back from boards with one empty square (each of the N*N possibilities) one can find optimal starting points (which will be a symmetric family).
If I were still teaching advanced programming, I would probably use this game.
--traveler | [reply] |
|
| [reply] |
|
| [reply] |
Re: Challenge: Box Blackout
by ikegami (Patriarch) on Jan 24, 2006 at 05:51 UTC
|
The following generates the solution using brute force. It works for 3x3, but takes forever for 10x10. It hasn't finished running for 10x10 yet, so I don't know if it gives a sensible answer.
use strict;
use warnings;
use re 'eval';
my $size = 3;
my $sizem1 = $size-1;
my $sizem2 = $size-2;
my $grid = 'X' x ($size*$size);
my %solution;
my @todo = $grid;
while (@todo) {
local $_ = pop(@todo);
next if $solution{$_}++;
# Row
/^((?:.{$size})*X{0,$size})X(X{0,$sizem1}(?:.{$size})*)$
(?{ push(@todo, "$1_$2") })(?=\Z=)/x;
# Col
/^(.{0,$sizem1}(?:X.{$sizem1})*)X((?:.{$sizem1}X)*.{0,$sizem1})$
(?{ push(@todo, "$1_$2") })(?=\Z=)/x;
# Diag \
/^((?:X.{$size})*)X((?:.{$size}X)*)$
(?{ push(@todo, "$1_$2") })(?=\Z=)/x;
# Diag /
/^(.{$sizem1}(?:X.{$sizem2})*)X((?:.{$sizem2}X)*.{$sizem1})$
(?{ push(@todo, "$1_$2") })(?=\Z=)/x;
}
my @solutions = map substr($_, 5),
sort { $b cmp $a }
map sprintf('%05d%s', 0+/_/g, $_),
keys %solution;
foreach my $solution (@solutions) {
print
map "$_\n\n",
join "\n",
map /(...)/g,
$solution;
}
A mirror image of a solution is counted as a solution.
| [reply] [d/l] |
Re: Challenge: Box Blackout
by Roy Johnson (Monsignor) on Jan 24, 2006 at 15:58 UTC
|
| [reply] [d/l] |
|
|