%Group Members
%02-025754
%02-025578
%01-015526

% Problem: To fill a 8 X 8 puzzle using a given number of quadrominoes.

puzzle(Moves,X_dim,Y_dim):-                  % Top level predicate used to solve puzzle using depth first 
  puzzle(64,64,64,64,64,Moves,X_dim,Y_dim).  % Maximum number of each piece that can be placed is 64
                        	             % since each piece occupies 4 cells 4(64) = 256
					     % biggest puzzle 256 cells.


puzzle(Nlines,Nls,Nts,Nzs,Nboxes,Moves,X_dim,Y_dim):- %initial state represented by a list of unoccupied              
       getfstate(Q,X_dim,Y_dim),
       solve(Nlines,Nls,Nts,Nzs,Nboxes,Q,Moves).

solve(_,_,_,_,_,State,[]):- % If there are no unoccupied cells then we are finished
    goal_state(State).


%solve predicate used for depth first search
solve(Nlines,Nls,Nts,Nzs,Nboxes,State,[First|Rest]):-
      good_move(Nlines,Nls,Nts,Nzs,Nboxes,First,State,Result,Nlines1,Nls1,Nts1,Nzs1,Nboxes1),
      fill_squares(Result,State,NewState),
      solve(Nlines1,Nls1,Nts1,Nzs1,Nboxes1,NewState,Rest).

goal_state([]).

      
% Given a piece along with an action, good_move gets the cells occupied
% by the  piece based on it's location, applies the action and tests if the
% resulting location cells are allowable  
good_move(Nlines,Nls,Nts,Nzs,Nboxes,[Piece,X,Y,Action],State,Result,Nlines1,Nls1,Nts1,Nzs1,Nboxes1):- 
	member((X,Y),State),
        get_cells(Nlines,Nls,Nts,Nzs,Nboxes,Piece,X,Y,Piececells,Nlines1,Nls1,Nts1,Nzs1,Nboxes1),
        apply_move(Piececells,Action,Result),
        allowable(Result,State).

% A piece is allowable if all it's cells are unoccupied
allowable([(A,B),(C,D),(E,F),(G,H)],State):-
           member((A,B),State),
           member((C,D),State),
	   member((E,F),State),
           member((G,H),State).

    
%*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
% Each  cell is flipped relative to it's starting location 
flip([(A,B),(C,D),(E,F),(G,H)],Flipped):-
	 flip1((A,B),(C,D),Cell2),
         flip1((A,B),(E,F),Cell3),
         flip1((A,B),(G,H),Cell4),
         Flipped = [(A,B),Cell2,Cell3,Cell4].



% To flip a cell horizontally about a location it's columnar displacement is
% negated     
flip1((_,Sy),(X,Y),(X,Dy)):-
        Dy is Sy - ( Y - Sy).


% Each cell is rotated about the origin. 
rotate([(A,B),(C,D),(E,F),(G,H)],Rotated):-
         rotate1((A,B),(C,D),Cell2),
         rotate1((A,B),(E,F),Cell3),
         rotate1((A,B),(G,H),Cell4),
         Rotated = [(A,B),Cell2,Cell3,Cell4].
         
% When rotating a cell about a location, vertical displacements
% are converted to horizontal displacement, and vice - versa
rotate1((SourceX,SourceY),(X,Y),(DestinationX,DestinationY)):-
        DestinationX is SourceX + Y - SourceY,
        DestinationY is SourceY - (X - SourceX).

% To fill cells, their positions a removed from the list of unoccupied cells
fill_squares([(A,B),(C,D),(E,F),(G,H)],State,NewState):-
             delete(State,(A,B),X),
             delete(X,(C,D),Y),
             delete(Y,(E,F),Z),
             delete(Z,(G,H),NewState).


%*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
% Used when no action is applied to cells
apply_move(X,-,X).
       
apply_move(X,rotate1,Y):-
         rotate(X,Y).

apply_move(X,rotate2,Y):-
         rotate(X,Z),rotate(Z,Y).
 
apply_move(X,rotate3,Y):-
         rotate(X,Z),rotate(Z,A),rotate(A,Y).

apply_move(X,flip,Y):- 
         flip(X,Y).

apply_move(X,frotate1,Y):-
    apply_move(X,flip,Z),
    apply_move(Z,rotate1,Y).

apply_move(X,frotate2,Y):-
    apply_move(X,flip,Z),
    apply_move(Z,rotate2,Y).

apply_move(X,frotate3,Y):-
    apply_move(X,flip,Z),
    apply_move(Z,rotate3,Y).

%*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-

% get_cells predicate used to get the cells that a piece would
% occupy given it's starting location

get_cells(Nlines,Nls,Nts,Nzs,Nboxes,line,X,Y,Piececells,Nlines1,Nls,Nts,Nzs,Nboxes):-
	 Nlines > 0,
         Nlines1 is Nlines - 1,
	 ColVar1 is Y + 1,
         ColVar2 is Y + 2,
	 ColVar3 is Y + 3,
         Piececells = [(X,Y),(X,ColVar1),(X,ColVar2),(X,ColVar3)].
      
get_cells(Nlines,Nls,Nts,Nzs,Nboxes,box,X,Y,Piececells,Nlines,Nls,Nts,Nzs,Nboxes1):-
	 Nboxes > 0,
         Nboxes1 is Nboxes - 1,
	 RowVar is X + 1,
         ColVar is Y + 1,
         Piececells = [(X,Y),(X,ColVar),(RowVar,Y),(RowVar,ColVar)].
       
get_cells(Nlines,Nls,Nts,Nzs,Nboxes,el,X,Y,Piececells,Nlines,Nls1,Nts,Nzs,Nboxes):-
	 Nls > 0,
         Nls1 is Nls - 1,
         RowVar is X + 1, 
         ColVar1 is Y + 1,
         ColVar2 is Y + 2,
         Piececells = [(X,Y),(X,ColVar1),(X,ColVar2),(RowVar,ColVar2)].
	
get_cells(Nlines,Nls,Nts,Nzs,Nboxes,tee,X,Y,Piececells,Nlines,Nls,Nts1,Nzs,Nboxes):-
	 Nts > 0,
         Nts1 is Nts - 1,
         RowVar is X + 1, 
         ColVar1 is Y + 1,
         ColVar2 is Y + 2,
         Piececells = [(X,Y),(X,ColVar1),(X,ColVar2),(RowVar,ColVar1)].
        
get_cells(Nlines,Nls,Nts,Nzs,Nboxes,zee,X,Y,Piececells,Nlines,Nls,Nts,Nzs1,Nboxes):-
         Nzs > 0,
         Nzs1 is Nzs - 1,
         RowVar is X + 1,
         ColVar1 is Y + 1,
         ColVar2 is Y + 2,
         Piececells = [(X,Y),(X,ColVar1),(RowVar,ColVar1),(RowVar,ColVar2)].

%*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
	
getfstate(X,X_dim,Y_dim):-
  bagof(Q,cells_in(X_dim,Y_dim,Q),X).

cells_in(X_dim,Y_dim,Out):-
  Q =[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],   
  member(X,Q),
  member(Y,Q),
  X=<X_dim,
  Y=<Y_dim,
  Out = (X,Y).