Re: Lights out puzzle

[salva]

Perl may not be the right tool to solve that problem.

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

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

[ambrus]

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

linear,
which is what my second solution uses.

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

like I noticed for my first solution, once you decide about the buttons of the first row, they determine all the other buttons easily. So much that if you write the program as a constraint program in the natural way, the constraint solver can also determine all the buttons from the ones in the first row, thus a constraint solution must be at least as fast as my first solution.

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