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

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

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?

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

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?

Thanks,

loris

---

"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.

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;
}
[download]

A mirror image of a solution is counted as a solution.