/*
	pentmino solver
	for SWI-PROLOG version 6.4.1
	2013/10/04
	written by Taku Koyahata
	mail:koyahata*koyahatataku.com(change * to @)
	This program is NOT a public domain software.
	But you can edit and redistribute this program on your own responsibility.
*/


:- dynamic
	gvar/2.

gvar(bd_width,11).
gvar(bd_height,6).
gvar(bd_wall,4).
gvar(bd_left,4).
gvar(bd_top,4).
gvar(bd_right,15).
gvar(bd_bottom,10).
gvar(area_cnt,0).
pent_main:-
	prepare_bd(Bd),
	prepare_pieces(Pieces),
	prepare_pieces_add_rotations_and_size(Pieces,Pieces1),
	depth_search(Bd,Pieces1).

depth_search(Bd,[]):-
	nl,write('cleared'),nl,
	print_bd(Bd).
depth_search(Bd,Pieces):-
	print_bd(Bd),nl,
	topleft_empty_square(Bd,VarLeft,VarTop),
%	format('empty topleft(~d,~d)\n',[VarLeft,VarTop]),
	select(SelPiece,Pieces,PiecesRest), % select piece
	select([Piece,PieceWidth,PieceHeight],SelPiece,_),% select rotation
	% select x,y position
	Xstart is VarLeft - PieceWidth + 1,
	Ystart is VarTop - PieceHeight + 1,
	between(Ystart,VarTop,Y), % select Y position
	between(Xstart,VarLeft,X), % select X position
	set_piece(Bd,Piece,X,Y),
	depth_search(Bd,PiecesRest).

% set piece to Board
set_piece(Bd,Piece,X,0):-
	!,set_lines(Bd,Piece,X).
set_piece([_|BdRest],Piece,X,Y):-
	Y1 is Y-1,
	set_piece(BdRest,Piece,X,Y1).

set_lines(_,[],_):-!.
set_lines([BdFirst|BdRest],[PieceFirst|PieceRest],X):-
	set_line(BdFirst,PieceFirst,X),
	set_lines(BdRest,PieceRest,X).

set_line(BdLine,PieceLine,0):-
	!,
	set_list(BdLine,PieceLine).
set_line([_|BdLineRest],PieceLine,X):-
	X1 is X-1,
	set_line(BdLineRest,PieceLine,X1).

set_list(_,[]):-!.
set_list([BdLineFirst|BdLineRest],[PieceLineFirst|PieceLineRest]):-
	BdLineFirst=PieceLineFirst,
	set_list(BdLineRest,PieceLineRest).

prepare_pieces_add_rotations_and_size([],[]):-!.
prepare_pieces_add_rotations_and_size(
	[ ShapeFirst | ShapesRest],
	[   [	[ShapeFirst,XFirst,YFirst],
		[Shape1,X1,Y1],
		[Shape2,X2,Y2],
		[Shape3,X3,Y3]   ]       |     OutRests]):-
	shape_rotate(ShapeFirst,Shape1),
	shape_rotate(Shape1,Shape2),
	shape_rotate(Shape2,Shape3),
	shape_size(ShapeFirst,XFirst,YFirst),
	shape_size(Shape1,X1,Y1),
	shape_size(Shape2,X2,Y2),
	shape_size(Shape3,X3,Y3),
	prepare_pieces_add_rotations_and_size(ShapesRest,OutRests).

prepare_bd(Bd):-
Bd=
[
[#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#],
[#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#],
[#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#],
[#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#],
[#,#,#,#,_,_,_,_,_,_,_,_,_,_,_,#,#,#,#],
[#,#,#,#,_,_,_,_,_,_,_,_,_,_,_,#,#,#,#],
[#,#,#,#,_,_,_,_,_,_,_,_,_,_,_,#,#,#,#],
[#,#,#,#,_,_,_,_,_,_,_,_,_,_,_,#,#,#,#],
[#,#,#,#,_,_,_,_,_,_,_,_,_,_,_,#,#,#,#],
[#,#,#,#,_,_,_,_,_,_,_,_,_,_,_,#,#,#,#],
[#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#],
[#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#],
[#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#],
[#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#]
].

prepare_pieces(Pieces):-
	Pieces = [
		[	[1,_,1],
			[1,1,1],
			[_,1,_]
		],
		[	[_,2,_,_,_],
			[2,2,2,2,2]
		],
		[	[3,3,3],
			[3,3,_],
			[3,_,_]
		],
		[	[4,_,_,_,_],
			[4,4,4,4,4]
		],
		[	[5,5,5],
			[_,_,5],
			[_,5,5]
		],
		[	[6,6,_,_,_],
			[_,6,6,6,6]
		],
		[	[_,7,_,_],
			[7,7,7,7],
			[_,7,_,_]
		],
		[	[_,8,_],
			[8,8,8],
			[8,_,_],
			[8,_,_]
		],
		[	[9,9,9,9],
			[9,_,9,_]
		],
		[	[a,a,a,_],
			[a,_,a,a]
		],
		[	[b,b,b,_],
			[_,b,b,b]
		]
	].
% del '#'
del_wall([],[]):-!.
del_wall([First|Rest],OutRest):-
	nonvar(First),
	First == '#',
	!,
	del_wall(Rest,OutRest).
del_wall([First|Rest],[First|OutRest]):-
	del_wall(Rest,OutRest).

print_bd_prepare([],[]):-!.
print_bd_prepare([BdLine|BdRest],[Lst|Rest]):-
	del_wall(BdLine,Lst),
	print_bd_prepare(BdRest,Rest).

% del []
print_bd_prepare2([],[]):-!.
print_bd_prepare2([First|BdRest],BdOutRest):-
	First==[],!,
	print_bd_prepare2(BdRest,BdOutRest).
print_bd_prepare2([First|BdRest],[First|BdOutRest]):-
	print_bd_prepare2(BdRest,BdOutRest).

print_bd(Bd):-
	print_bd_prepare(Bd,Bd1),
	print_bd_prepare2(Bd1,Bd2),
	print_bd_lines(Bd2),nl.

print_bd_lines([]):-!.
print_bd_lines([First|Rest]):-
	print_bd_sub(First),nl,
	print_bd_lines(Rest).

print_bd_sub([]):-!.
print_bd_sub([First|Rest]):-
        var(First),!,write(' .'),
        print_bd_sub(Rest).
print_bd_sub([First|Rest]):-
        format(' ~a',[First]),
        print_bd_sub(Rest).
set_gvar(Name,X):-
        nonvar(Name),retract(gvar(Name,_)),!,asserta(gvar(Name,X)).
set_gvar(Name,X):-
        nonvar(Name),asserta(gvar(Name,X)).

shape_size([First|Rest],Width,Height):-
	length(First,Width),
	length([First|Rest],Height).

shape_rotate(InShape,OutShape):-
	reverse(InShape,Shape1),
	shape_rotate_sub(Shape1,OutShape).

shape_rotate_sub([[]|_],[]):-!.
shape_rotate_sub(In,[Firsts|OutRests]):-
	maplist(get_first_and_rest,In,Firsts,Rests),
	shape_rotate_sub(Rests,OutRests).

has_var([First|_],0):-
	var(First),!.
has_var([_|Rest],Num):-
	has_var(Rest,Num1),
	Num is Num1 + 1.

% get topleft empty square position
topleft_empty_square(Bd,X,Y):-
	gvar(bd_width,Width),
	gvar(bd_height,Height),
	gvar(bd_wall,Wall),
	Min is Wall + Wall,
	Max is Min + Width -1 + Height - 1,
	between(Min,Max,AddVal),
	get_ymin_ymax(AddVal,Ymin,Ymax),
	between(Ymin,Ymax,Y),
	X is AddVal - Y,
	get_xy(Bd,X,Y,Val),
	var(Val),!.

get_ymin_ymax(AddVal,Ymin,Ymax):-
	gvar(bd_width,Width),
	gvar(bd_height,Height),
	gvar(bd_wall,Wall),
	((AddVal>Width+Wall-1)->
			(Ymin is AddVal - (Wall + Width - 1));
			(Ymin is Wall)
	),
	((AddVal<Wall+Height-1)->
			(Ymax is AddVal - Wall);
			(Ymax is Wall + Height - 1 )
	).

get_first_and_rest([First|Rest],First,Rest).

get_xy([BdLine|_],X,0,Val):-!,nth0(X,BdLine,Val),true.
get_xy([_|BdRest],X,Y,Val):-
        Y1 is Y-1,
        get_xy(BdRest,X,Y1,Val).

set_xy([BdLine|_],X,0,Val):-!,set_member(BdLine,X,Val),true.
set_xy([_|BdRest],X,Y,Val):-
        Y1 is Y-1,
        set_xy(BdRest,X,Y1,Val).

% set_member(List+,Nth+,SetVal+)
% set Nth of List to SetVal.
% fail if the member is not a Free Variable
set_member([Val|_],0,Val):-!,true.
set_member([_|Rest],Num,Val):-
        Num1 is Num-1,
        set_member(Rest,Num1,Val).