Re: Lights out puzzle

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).
[download]

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

Comment on Re: Lights out puzzle Download Code

Replies are listed 'Best First'.
Re^2: Lights out puzzle by ambrus (Abbot) on Nov 29, 2011 at 14:52 UTC
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.)	[reply]

Replies are listed 'Best First'.

Re^2: Lights out puzzle
by ambrus (Abbot) on Nov 29, 2011 at 14:52 UTC

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

my second solution

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

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

[reply]