# 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);