Re^2: Lights out puzzle (non-non-perl solution)

[salva]

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

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