use 5.014; use warnings;
our($R, $C, $M) = (14, 14, 7);
if (@ARGV) {
    3 == @ARGV or die "Usage: lights R C M";
    ($R, $C, $M) = map int, @ARGV;
}
my @c = (($C) x ($R-1), $C-$M);
my @m = map { (1<<$_)-1 } @c;
T: for my $t (0 .. $m[0]) {
    my @b; my @l = @m;
    for my $r (0 .. $R-1) {
        my $b = $b[$r] = $r <= 0 ? $t : $m[$r] & $l[$r-1];
        $r+1 < $R and $l[$r+1] ^= $m[$r+1] & $b;
        $l[$r] ^= $m[$r] & ($b<<1 ^ $b ^ $b>>1);
        0 <= $r-1 and $l[$r-1] ^= $m[$r-1] & $b;
    }
    0 == $l[$R-1] && 0 == $l[$R-2] or next T;
    say "Found solution: [";
    for my $r (0 .. $R-1) {
        for my $c (0 .. $C-1) {
            print " ", ($c[$r] <= $c ? " " : $b[$r]>>$c & 1 ? "P" : ".
+");
        }
        if (0) {
            print "  > ";
            for my $c (0 .. $C-1) {
                print " ", ($c[$r] <= $c ? " " : $l[$r]>>$c & 1 ? "*" 
+: ".");
            }
        }
        say "";
    }
    say "]";
}
say "done searching (R=$R, C=$C, M=$M).";
__END__
[download]

Example output.

Found solution: [
 . P . P . . . P . P . . . .
 . . P . . P . . P . . P P P
 P P . P . . . P . P . P . P
 P P . . . . . . . . P P . P
 . . . . P P P . P P P . P P
 . . P . P . P P P . . . P .
 P . . P P . . . . P . . P P
 . . P P . . . . P . . . . P
 . . P . P P P . . P P P P P
 P . P . P . P . P P . . . .
 . P P P P . P P P . P . . .
 P P P . . P . . . . . . P P
 P P . P P . P . . P . . P P
 . . . P P . .              
]
done searching (R=14, C=14, M=7).
[download]

The idea of this code is that once you know what buttons to push in the first row, it's trivial to compute what buttons you should push in all the other rows. You go from top to bottom, and in each row you press the buttons where the light in the row just above is lit.

So our algorithm (the algorithm I was alluding to in the spoiler of the original post) is to simply try out all combinations of buttons to press in the top row and see which ones work. Most of them won't work because some lights will remain lit in the bottom two rows.

A trick that makes the code shorter is that we're representing a row of lights or buttons as bits in a single integer. This way, the flipping of lights is easier to describe because fewer loops are needed. This is still not the shortest way to write code, because I wanted to keep it understandable.

To understand the code, comment out the line with next T;, enable the branch that dumps @c, and run for smaller inputs such as 4 3 1 or 6 5 2.