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

We're using the GAP computer algebra system as a tool. Download this program and save it as say `lights.g`. Load it in a GAP session either by giving the filename as a command-line argument when you start gap, or by executing the statement `Read("lights.g");`. Then try `lightout(14, 14, 7);` to get the solution to the original challenge.

In general, `lightout(r, c, m);` will show one solution for a board with r rows and c columns with the last m cells of the last column missing. The three arguments work the same as in my previous solution, but this time I print only one solution, not all of them.

`# lights out, see http://www.perlmonks.com/?node_id=940327
lightout := function(nr, nc, nm)
local onbd, forbd, linbd, nlin, wirelin, lightlin, sollin, solbd;
onbd := function(r, c)
return 1 <= r and r <= nr and 1 <= c and c <= nc and
(r < nr or c <= nc - nm);
end;
forbd := function(f)
local r, c;
for r in [1 .. nr - 1] do
for c in [1 .. nc] do
f(r, c);
od;
od;
for c in [1 .. nc - nm] do
f(nr, c);
od;
end;
linbd := List([1 .. nr], c -> []);
nlin := 0;
forbd(function (r, c)
nlin := nlin + 1;
linbd[r][c] := nlin;
end);
wirelin := NullMat(nlin, nlin, GF(2));
forbd(function (r, c)
local d, r1, c1;
for d in [[0, 0], [0, 1], [0, -1], [1, 0], [-1, 0]] do
r1 := r + d[1]; c1 := c + d[2];
if onbd(r1, c1) then wirelin[linbd[r][c]][linbd[r1][c1]] := Z(
+2); fi;
od;
end);
lightlin := List([1 .. nlin], c -> Z(2)); # all lamps lit
ConvertToVectorRep(lightlin);
#sollin := lightlin / wirelin;
sollin := SolutionMat(wirelin, lightlin);
solbd := List(linbd, v -> sollin{v});
Print("Found a solution for (R=", nr, ", C=", nc, ", M=", nm, ")\n");
Display(solbd);
end;
# try this for example:
#lightout(14, 14, 7);
`

Example session:

`gap> lightout(14, 14, 7);
Found a solution for (R=14, C=14, M=7)
. 1 . 1 . . . 1 . 1 . . . .
. . 1 . . 1 . . 1 . . 1 1 1
1 1 . 1 . . . 1 . 1 . 1 . 1
1 1 . . . . . . . . 1 1 . 1
. . . . 1 1 1 . 1 1 1 . 1 1
. . 1 . 1 . 1 1 1 . . . 1 .
1 . . 1 1 . . . . 1 . . 1 1
. . 1 1 . . . . 1 . . . . 1
. . 1 . 1 1 1 . . 1 1 1 1 1
1 . 1 . 1 . 1 . 1 1 . . . .
. 1 1 1 1 . 1 1 1 . 1 . . .
1 1 1 . . 1 . . . . . . 1 1
1 1 . 1 1 . 1 . . 1 . . 1 1
. . . 1 1 . .
gap>
`

Here, we are representing the game as the matrix `wirelin` over GF(2). The element `wirelin[u][v]` is 1 if and only if the button on field u toggles the light on field v. (Here, the fields on the game board are indexed with single integers assigned sequentially. The matrix `wirelin` is, incidentally, symmetric.) Thus, if `b` is a vector of GF(2) elements telling which buttons you push, `b*wirelin` will be the vector of which lights are toggled. To determine how to toggle all lights, we thus just have to solve the linear equation `b*wirelin = lightlin` over `GF(2)`, where `lightlin` is an all-one vector.

Now solving a linear equation over `GF(2)` is something apparently very few libraries can do, which is why I chose GAP which has a function for this.

This solution thus works in time polynomial in the size of the game board. Also, all the heavy loops are done inside the GAP core, which is optimized well. (Of course, it's probably possible to make even faster programs if you want to solve very large boards, but I don't think we'll need that.) No wonder for large boards, say 30x30, it finishes much faster than my previous solution, as that would have to try 2**30 starting positions.

Update: this might not be very idiomatic GAP. I don't have much practice in programming GAP, in particular I don't know the libraries enough and also I can't wrap my head around one-based indexing of lists.

Comment onLights out puzzleSelectorDownloadCode