Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:

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.

Cheers - L~R

Replies are listed 'Best First'.
Re: Challenge: Box Blackout (solved)
by tye (Sage) on Jan 24, 2006 at 00:43 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.
      1. 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.
      2. 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.
      3. 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.
      4. 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:
      1. Does it work?
      2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
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.


      I'm not too familiar with algorithm nomenculature, but if starting with a full board and working backward is an inverse backtrack, what would a non-inverse backtrack entail?



      "It took Loris ten minutes to eat a satsuma . . . twenty minutes to get from one end of his branch to the other . . . and an hour to scratch his bottom. But Slow Loris didn't care. He had a secret . . ."
        Well, a backtracking algorithm means working toward a solution, and, when you reach a dead end, going back to the last time you made a "choice". In many computer science classes students learn to implement a backtracking algorithm by solving the "Eight Queens Problem". You can google for that or check a CS text.

        The reason this is "inverse" is because you are starting with the "solution". I think that would be faster and easier to write, personally, but I might be wrong.

Re: Challenge: Box Blackout
by ikegami (Pope) 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.

Re: Challenge: Box Blackout
by Roy Johnson (Monsignor) on Jan 24, 2006 at 15:58 UTC