My immediate reaction would be to press the button on the wall socket/power source, no power to the board, no lights :P

Good Monday morning also to you, ambrus!

Lights out is really nice. Especially the simplicity of the solution: if it is solvable (not all board-configurations are), it takes at maximum n*m turns on an n-by-m board. However when I try it manually, I need many, many more (if I ever finish it) ...

Rata (who's only adventure into VB-for-Excel-programming was a 5x5 - version of this game)

A generic solution using GNU-Prolog (that has a very fast finite domain constraint solver):

lights_on(Len, W, Sol) :-
        length(Sol, Len),
        fd_domain_bool(Sol),
        make_constraints(0, Len, W, Sol),
        fd_labeling(Sol).

print_sol(W, Sol) :-
        length(L, W),
        (   append(L, T, Sol)
        ->  write(L),
            nl,
            print_sol(W, T)
        ;   write(Sol),
            nl ).
        

make_constraints(Ix, Len, W, Sol) :-
        (   Ix == Len
        ->  true
        ;   make_constraint(Ix, W, Sol),
            Ix1 is Ix + 1,
            make_constraints(Ix1, Len, W, Sol)).

nth0(Ix, L, Var) :-
        Ix1 is Ix + 1,
        nth(Ix1, L, Var).

up(Ix, W, Sol, Var) :-
        Ix1 is Ix - W,
        (   nth0(Ix1, Sol, Var)
        ->  true
        ;   Var = 0 ).

down(Ix, W, Sol, Var) :-
        Ix1 is Ix + W,
        (   nth0(Ix1, Sol, Var)
        ->  true
        ;   Var = 0 ).

left(Ix, W, Sol, Var) :-
        Ix1 is Ix - 1,
        (   Ix1 // W =:= Ix // W,
            nth0(Ix1, Sol, Var)
        ->  true
        ;   Var = 0).

right(Ix, W, Sol, Var) :-
        Ix1 is Ix + 1,
        (   Ix1 // W =:= Ix // W,
            nth0(Ix1, Sol, Var)
        ->  true
        ;   Var = 0).

make_constraint(Ix, W, Sol) :-
        nth0(Ix, Sol, This),
        up(Ix, W, Sol, Up),
        down(Ix, W, Sol, Down),
        right(Ix, W, Sol, Right),
        left(Ix, W, Sol, Left),
        This ## Up ## Down ## Right ## Left.

test :-
        W = 14,
        H = 14,
        Missing = 7,
        Len is W * H - Missing,
        lights_on(Len, W, Sol),
        print_sol(W, Sol).

[download]

It solves any problem where N < 20 in a few seconds.

This is a nice solution.

I too was thinking that perl might not be the best tool for solving this, but for an entirely different reason. I wasn't thinking of this puzzle as a constraint satisfaction problem. Of course not, since it's

<Reveal this spoiler or all spoilers in this node or all in this thread>
which is what my second solution uses.

But once you mentioned it, viewing as a constraint satisfaction problem also makes sense. After all,

<Reveal this spoiler>

Update: for reference, the last time salva has surprised me with a nice solution using a finite domain constraint solver was Re^4: Seven by seven farming puzzle.

Update: I ran the solution for (20, 20, 2). Your prolog solution took two and a half minutes (I have modified the printing part somewhat, but used GNU prolog). My perl solution took 40 seconds. So my opinion is that this prolog+finite-domain solution is fast enough. (Update: the same solution ran in SWI prolog is riddiculously slow though.)

You may view the original node and the consideration vote tally.

Here's a quick Monday morning puzzle.

Here are some comments on how it works:
The code clears all the lines except for the last one (clean) the simple way: if there is a light, click underneath. The last line (or, better to say, broken line, i.e. the last line plus the remaining half of the previous one) is then solved half-randomly. At the beginning, I cache how clicking on the top line influences the last line, but only for one click on the line (i.e. I only know what the last line will be after having one light lit). Therefore, I have to click randomly until I get a cached position that I can solve. This works well for size 14, but the time doubles for each +2 in size, so size 20 is already too slow. Caching more positions could be added easily (like clicking two times), but I am not sure how much time it would take to cache all possible combinations on the first line.
Because the order of clicks is not important, I keep a separate map of the board with 0 for the even clicks and 1 for the odd ones. This separate board is the output of the program.

I changed the definition of the show and toggle methods like this:

sub show {
    my $board = shift;
    print "\e[H";
    for my $row (@$board) {
        return unless defined $row;
        print map $_ ? '*' : defined $_ ? '.' : '', @$row;
        print "\e[K\n";
    }
    print "\e[J";
    use Time::HiRes "sleep";
    sleep(6e-3);
} # show

sub toggle {
    my ($board, $x, $y) = @_;
    my $old = $board->[$y][$x];
    return unless defined $old;
    $board->[$y][$x] = $old eq 1 ? 0 : 1;
} # toggle

[download]

and now I can see the lights being chased down to the bottom of the board. Looks nice.

Yes, in fact, I did something similar for debugging :-)

Here's a solution written in perl, then some explanation on how it works.

Now quick someone bribe zentara to put a TK interface to this... and I'll get nothing done for the next week. :)

You may view the original node and the consideration vote tally.

Here's a non-perl solution, with explanation.

For larger boards, this one is much faster than my program above. (You could try (29, 30, 2) or (39, 40, 2) as large examples where there's a unique button combination this program finds very quickly but that would take ages to found with the previous program.)

Now solving a linear equation over GF(2) is something apparently very few libraries can do

That's quite easy to implement, so easy that, well... see Algorithm::GaussianElimination::GF2.

Using that module, the Lights On problem gets reduced to:

use strict;
use warnings;

use Algorithm::GaussianElimination::GF2;

use 5.010;

(@ARGV >= 1 and @ARGV <= 2) or die "Usage:\n  $0 len [width]\n\n";

my ($len, $w) = @ARGV;

unless (defined $w) {
    $w = int sqrt($len);
    $w++ unless $w * $w == $len;
}

my $a = Algorithm::GaussianElimination::GF2->new;

for my $ix (0..$len-1) {
    my $eq = $a->new_equation;

    $eq->b(1);
    $eq->a($ix, 1);
    my $up = $ix - $w;
    $eq->a($up, 1) if $up >= 0;
    my $down = $ix + $w;
    $eq->a($down, 1) if $down < $len;
    my $left = $ix - 1;
    $eq->a($left, 1) if $left % $w + 1 != $w;
    my $right = $ix + 1;
    $eq->a($right, 1) if $right % $w and $right < $len;
}

my ($sol, @base0) = $a->solve;

if ($sol) {
    my @sol = @$sol;
    while (@sol) {
        my @row = splice @sol, 0, $w;
        say "@row";
    }

    for my $sol0 (@base0) {
        say "sol0:";
        my @sol0 = @$sol0;
        while (@sol0) {
            my @row = splice @sol0, 0, $w;
            say "@row";
        }
    }
}
else {
    say "no solution found"
}
[download]

On my computer the 14x14-7 problem gets solved in 0.06 seconds.