/*
FlipEm.pl
A constraint-based solver for the FlipEm game
See: http://www.innograte.com/mobile/midp/ for the mobile phone game.
version 0.2 - (C) 2006 - Andrea Sterbini
This file is released under the GNU GPL license.
FlipEm is a game where you must turn a 0-filled NxN boolean matrix into a 1-filled matrix
Moves: you flip the bit of a cell together with the bits of the 4 neighbors (above/below and left/right)
(if a cell is on the border you flip less neighbors)
Goal: find the minimum number of proper cells to switch (with their neighbors)
Solution:
- build two lists of variables:
- a bit for each cell where a move is centered
- the sum of the neighbors moves that switch this cell
- do not flip the neighbors, count instead how many moves have been made in a cell neighborhood
- impose the contraints:
- the sum of a given cell is the sum of the neighbors where a move has been made
- bits are boolean (0,1)
- each sum is odd
- count the total number of moves done
- find a labeling of the moves that minimizes the number of moves done
HOW TO USE:
- start GNU Prolog
- consult the FlipEm.pl file
- call the go(N,Shape) predicate (with Shape = '+', 'X', 'O', 'L', 'Y', '\\')
HISTORY
v. 0.1 - first implementation
v. 0.2 - extended to handle '+', 'X', 'O', 'L', 'Y', '\' neighborhoods
TODO
- extend to other neighborhood structures (hexagonal grid, 3D grid)
*/
%%%
%%% main predicate, N is the size of the board
%%% Usage:
%%% go(N) classic '+' neighborhood
%%% go(N,Shape) with Shape = '+', 'X', 'O', 'L', 'Y', '\\'
go(N) :-
go(N,'+').
go(N,Shape) :-
go(N,Shape,_Moves,_B).
go(N,Shape,Moves,B) :-
nonvar(N),
nonvar(Shape),
var(Moves),
var(B),
generate_table(N,Shape,Cells,Neighbors,Counts),
fd_domain_bool(Cells), % cells can be '1' (move done) or '0' (no move here)
constrain_neighbors(Neighbors), % compute sums of neighboring moves
constrain_sums(Counts), % all sums must be odd
sum(Cells,Moves), % count the number of moves
Options = [backtracks(B)],
fd_minimize(fd_labeling(Cells, Options),Moves), % find a pattern that minimizes Moves
format("Found a solution with a minimum of %d moves\n",[Moves]),
show(Cells, N), % print the moves
format("How many times the cells have been switched:\n",[]),
show(Counts, N). % print the sums
%%% somma(L,S).
%%% constraint S to be the sum of the elements of list L
%%%
sum([],0).
sum([H|T],S) :-
S #=# S1 + H ,
sum(T,S1).
%%%
%%% create a list of N^2 variables
%%%
generate_cells(N,Cells) :-
N2 is N * N,
length(Cells,N2).
%%%
%%% build the groups of neighbors
%%%
generate_neighbors(N,Shape,Counts,Cells,Neighbors) :-
bagof( X:Neigh,
I^(nth(I,Cells,X),
bagof( Y,
J^(near(Shape,N,I,J),nth(J,Counts,Y)),
Neigh)),
Neighbors).
%%%
%%% compute the index of the neighbors
%%% nth uses indexes in the [1..N] range
%%%
%%%
%%% '+'-shaped neighborhood
%%%
offset('+', 0, -1).
offset('+', -1, 0).
offset('+', 0, 0).
offset('+', +1, 0).
offset('+', 0, +1).
%%%
%%% 'X'-shaped neighborhood
%%%
offset('X', -1, -1).
offset('X', +1, -1).
offset('X', 0, 0).
offset('X', -1, +1).
offset('X', +1, +1).
%%%
%%% 'O'-shaped neighborhood
%%%
offset('O', -1, -1).
offset('O', 0, -1).
offset('O', +1, -1).
offset('O', -1, 0).
offset('O', +1, 0).
offset('O', -1, +1).
offset('O', 0, +1).
offset('O', +1, +1).
%%%
%%% 'Y'-shaped neighborhood
%%%
offset('Y', -1, -1).
offset('Y', +1, -1).
offset('Y', 0, 0).
offset('Y', 0, +1).
%%%
%%% 'L'-shaped neighborhood
%%%
offset('L', 0, -1).
offset('L', 0, 0).
offset('L', +1, 0).
%%%
%%% '\'-shaped neighborhood
%%%
offset('\\', -2, -2).
offset('\\', -1, -1).
offset('\\', 0, 0).
offset('\\', +1, +1).
offset('\\', +2, +2).
near(Shape, N, I, J) :-
offset(Shape, DX, DY),
(
DX < 0, (I - 1) mod N >= - DX
;
DX > 0, (N - I) mod N >= DX
;
DX = 0
),
J is I + DX + DY*N,
J > 0,
J =< N*N.
%%%
%%% build variables
%%%
generate_table(N,Shape,Cells,Neighbors,Counts) :-
generate_cells(N,Cells),
generate_cells(N,Counts),
generate_neighbors(N,Shape,Cells,Counts,Neighbors).
%%%
%%% print a table
%%%
show([],_) :- nl.
show(Cs,N) :-
show_line(Cs,C1s,N),
show(C1s,N).
%%%
%%% print a table line
%%%
show_line(Cs, Cs, 0) :-
!,
format("|\n",[]).
show_line([C|Cs], C1s, N) :-
N1 is N - 1,
(C == 0 ->
format("| ",[])
;
format("|~p",[C])),
show_line(Cs, C1s, N1).
%%%
%%% constraint each sum variable to be the sum of the neighboring cells
%%%
constrain_neighbors([]).
constrain_neighbors([S:V|T]) :-
sum(V,S),
constrain_neighbors(T).
%%%
%%% each sum is odd
%%%
constrain_sums([]).
constrain_sums([C|T]) :-
1 #= C rem 2,
constrain_sums(T).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% THE END %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%