Sunday 3 August 2008

Lights out solver using CLP


:- use_module(library(clpfd)).

solve(Puzzle,Solution) :-
dimensions(Puzzle,Rows,Cols), dimensions(Solution,Rows,Cols),
flatten(Solution,Variables), Variables ins 0..1,
cells_of(Puzzle --> configure(Solution)), label(Variables).

configure(Solution,(X,Y,o)) :- around(X,Y,Solution,Group), off(Group).
configure(Solution,(X,Y,*)) :- around(X,Y,Solution,Group), on(Group).

on(Lights) :- sum(Lights, #=, On), 1 #= On mod 2.
off(Lights) :- sum(Lights, #=, Off), 0 #= Off mod 2.

around(X,Y,Grid,[Up,Left,Down,Right,Middle]) :-
Yu is Y-1, Xl is X-1,
Yd is Y+1, Xr is X+1,
( Grid@([Yu,X]->Up) -> true ; Up = 0 ),
( Grid@([Y,Xl]->Left) -> true ; Left = 0 ),
( Grid@([Yd,X]->Down) -> true ; Down = 0 ),
( Grid@([Y,Xr]->Right) -> true ; Right = 0 ),
( Grid@([Y,X]->Middle) -> true ; Middle = 0 ).

game([[*,o,o,o,o,o,*,o],
[*,*,o,*,*,*,*,*],
[*,*,o,*,*,*,o,*],
[*,o,o,o,o,o,o,o],
[o,*,*,o,o,o,*,*],
[o,*,o,o,o,o,o,o],
[*,*,*,*,*,*,o,o],
[o,*,*,*,*,*,*,*]]).





:- op(500,xfy,@).
:- op(1050,yfx,<-).

flatten([],[]).
flatten([X|Xs],Zs) :- flatten(Xs,Ys), append(X,Ys,Zs).

flip(P,Y,X) :- call(P,X,Y).
dimensions(Grid, Rows, Cols) :- length(Grid, Rows), maplist(flip(length,Cols),Grid).

E@([]->E) :- !.
[X|_]@([0|Ns]->E) :- !, X@(Ns->E).
[_|X]@([N|Ns]->E) :- !, N > 0, succ(M, N), X@([M|Ns]->E).

_/E@([]<-E) :- !.
[X|Xs]/[Y|Xs]@([0|Ns]<-E) :- !, X/Y@(Ns<-E).
[X|Xs]/[X|Ys]@([N|Ns]<-E) :- !, N > 0, succ(M, N), Xs/Ys@([M|Ns]<-E).

tuple(Board,Tuples) :- tuple((0,0),Board,Tuples).
tuple(_,[],[]).
tuple((X,Y),[Row|Rows],Tuples) :-
tuprow((X,Y),Row-Tail,Tuples),
succ(Y,Y1), tuple((X,Y1),Rows,Tail).
tuprow(_,[]-X,X).
tuprow((I,J),[E|Es]-X,[(I,J,E)|Xs]) :- succ(I,I1),tuprow((I1,J),Es-X,Xs).

cells_of(Grid --> Pred) :- tuple(Grid, Tuples), maplist(Pred, Tuples).

1 comment:

Cory Shelton said...

Great post thhank you