/*
	number area solver
	for SWI-PROLOG version 6.4.1
	2013/10/04
	written by Taku Koyahata 2013/10/04
	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.
	
  abbreviations
	wh - width and height
	rct - rectangle
*/
:- dynamic
        gvar/2.

set_gvar(Name, X) :-
    nonvar(Name), retract(gvar(Name, _)), !, asserta(gvar(Name, X)).
set_gvar(Name, X) :-
    nonvar(Name), asserta(gvar(Name, X)).

% convert area to [width,height]
area2wh(2,[1,2]).   area2wh(2,[2,1]).
area2wh(3,[1,3]).   area2wh(3,[3,1]).
area2wh(4,[1,4]).   area2wh(4,[2,2]).  area2wh(4,[4,1]).
area2wh(5,[1,5]).   area2wh(5,[5,1]).
area2wh(6,[1,6]).   area2wh(6,[2,3]).  area2wh(6,[3,2]).  area2wh(6,[6,1]).
area2wh(7,[1,7]).   area2wh(7,[7,1]).
area2wh(8,[1,8]).   area2wh(8,[2,4]).  area2wh(8,[4,2]).  area2wh(8,[8,1]).
area2wh(9,[1,9]).   area2wh(9,[3,3]).  area2wh(9,[9,1]).
area2wh(10,[1,10]). area2wh(10,[2,5]). area2wh(10,[5,2]). area2wh(10,[10,1]).
area2wh(12,[1,12]). area2wh(12,[2,6]). area2wh(12,[3,4]). area2wh(12,[4,3]).
area2wh(12,[6,2]).  area2wh(12,[12,2]).

initial_bd(Bd):-
	!,
/*
	Bd = bd(
		hline(7,_,_,_,_,_,_,_,_,8),
		hline(_,_,_,_,9,5,_,_,_,_),
		hline(_,5,_,_,_,_,_,_,4,_),
		hline(_,_,_,6,_,_,8,_,_,_),
		hline(_,_,_,_,_,_,_,_,_,_),
		hline(_,_,_,_,_,_,_,_,_,_),
		hline(_,_,_,10,_,_,9,_,_,_),
		hline(_,3,_,_,_,_,_,_,6,_),
		hline(_,_,_,_,4,2,_,_,_,_),
		hline(6,_,_,_,_,_,_,_,_,8)
	),
*/
Bd = bd(
hline(_,_,4,_,_,_,_,6,_,_,_,_,_,12,_,_,_,_,_,_,_,8,_,_,_,_,_,_,_,_,6,_,_,_,_,6),
hline(_,4,_,_,_,_,5,_,_,_,_,_,4,_,_,_,_,_,_,3,5,_,_,_,_,_,_,_,_,6,_,_,_,_,8,_),
hline(4,_,_,_,4,_,_,_,_,_,10,_,_,_,_,_,_,6,8,_,_,_,_,_,_,9,3,4,_,_,_,_,_,8,_,_),
hline(_,_,_,6,_,_,_,_,_,_,_,2,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,10,_,_,_,_),
hline(_,_,_,_,_,_,_,_,_,6,_,_,_,_,_,4,_,_,_,_,_,12,6,_,_,_,_,_,_,_,6,_,_,_,_,_),
hline(_,8,_,_,4,2,8,_,4,_,_,_,_,_,4,_,_,_,_,_,_,_,_,4,_,_,_,_,4,_,_,_,_,_,_,_),
hline(5,_,_,_,_,_,_,_,_,_,_,_,_,6,_,_,_,_,_,_,_,_,_,3,_,_,_,8,_,_,_,_,_,_,_,8),
hline(_,_,_,_,_,_,_,_,_,_,_,_,4,_,_,_,8,_,_,_,4,_,_,_,_,_,_,_,_,_,_,_,_,_,6,_),
hline(_,_,_,8,_,_,_,_,_,_,8,_,_,_,_,6,_,_,_,6,_,_,_,_,_,4,_,_,_,_,6,6,6,_,_,_),
hline(_,_,9,_,_,_,_,4,_,_,_,_,_,4,_,_,_,_,_,_,_,_,2,_,_,_,_,_,8,_,_,_,_,_,_,_),
hline(_,_,_,_,_,_,_,8,_,_,_,_,_,9,_,_,_,_,_,_,_,_,4,_,_,_,_,_,8,_,_,_,_,4,_,_),
hline(_,_,_,6,8,8,_,_,_,_,9,_,_,_,_,_,9,_,_,_,9,_,_,_,_,8,_,_,_,_,_,_,8,_,_,_),
hline(_,6,_,_,_,_,_,_,_,_,_,_,_,_,_,4,_,_,_,12,_,_,_,6,_,_,_,_,_,_,_,_,_,_,_,_),
hline(6,_,_,_,_,_,_,_,6,_,_,_,6,_,_,_,_,_,_,_,_,_,6,_,_,_,_,_,_,_,_,_,_,_,_,4),
hline(_,_,_,_,_,_,_,4,_,_,_,_,6,_,_,_,_,_,_,_,_,8,_,_,_,_,_,4,_,4,6,6,_,_,10,_),
hline(_,_,_,_,_,7,_,_,_,_,_,_,_,12,6,_,_,_,_,_,9,_,_,_,_,_,3,_,_,_,_,_,_,_,_,_),
hline(_,_,_,_,4,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,6,_,_,_,_,_,_,_,4,_,_,_),
hline(_,_,6,_,_,_,_,_,4,6,4,_,_,_,_,_,_,4,4,_,_,_,_,_,_,8,_,_,_,_,_,4,_,_,_,3),
hline(_,4,_,_,_,_,6,_,_,_,_,_,_,_,_,6,6,_,_,_,_,_,_,8,_,_,_,_,_,4,_,_,_,_,4,_),
hline(4,_,_,_,_,6,_,_,_,_,_,_,_,_,8,_,_,_,_,_,_,_,6,_,_,_,_,_,7,_,_,_,_,3,_,_)
),

	functor(Bd,_,BdHeight),
	arg(1,Bd,HLine),
	functor(HLine,_,BdWidth),
	set_gvar(bd_width,BdWidth),
	set_gvar(bd_height,BdHeight).

sikaku_main:-
	initial_bd(InitialBd),
	bd2areaLst(InitialBd,AreaLst),
	make_solving_bd(AreaLst,SolvingBd),
	Xc is 1, Yc is 1,
	reverse(AreaLst,NewAreaLst),
	depth_search(SolvingBd,[Xc,Yc],NewAreaLst).

% make solving bd from AreaLst
make_solving_bd(AreaLst,SolvingBd):-
	gvar(bd_width,BdWidth),
	gvar(bd_height,BdHeight),
	functor(SolvingBd,bd,BdHeight),
	Yc is 1,
	YEnd is BdHeight,
	make_bd_sub(SolvingBd,BdWidth,Yc,YEnd),
	init_solving_bd(SolvingBd,AreaLst).

init_solving_bd(_,[]).
init_solving_bd(SolvingBd,[[AreaID,_,Xc,Yc]|Rest]):-
	!,
	arg(Yc,SolvingBd,HLine),
	arg(Xc,HLine,Square),
	Square is AreaID,
	init_solving_bd(SolvingBd,Rest).

make_bd_sub(_,_,Yc,YEnd):-
	Yc > YEnd,
	!.
make_bd_sub(Bd,BdWidth,Yc,YEnd):-
	!,
	arg(Yc,Bd,Val),
	functor(Val,hline,BdWidth),
	Yn is Yc + 1,
	make_bd_sub(Bd,BdWidth,Yn,YEnd).

depth_search(Bd,[Xc,Yc],AreaLst):-
%	nl,
%	print_bd(Bd),
	arg(Yc,Bd,HLine),
	arg(Xc,HLine,AreaID),
%	bd_xy(Bd,Xc,Yc,AreaID),
	(   (var(AreaID))->
		(  select([AreaID,Area,X_area,Y_area],AreaLst,RestArea),

		   Xdif is abs(Xc-X_area),
		   Xdif < Area, % narrowing search
		   Ydif is abs(Yc-Y_area),
		   Ydif < Area, % narrowing search,
		   area2wh(Area,[Width,Height]),
		   Xdif < Width, Ydif < Height,
		   X2 is X_area, Y2 is Y_area
		);
		(  select([AreaID,Area,Xc,Yc],AreaLst,RestArea),
		   area2wh(Area,[Width,Height]),
		   X2 is Xc, Y2 is Yc
		)
	),

	topleft_of_rct_including_2_pts([Xc,Yc],[X2,Y2],
					[Width,Height],[Left,Top]),
	set_rect(Bd,[Top,Left,Width,Height],AreaID),
	next_xy(Bd,[Xc,Yc],[Xn,Yn]),
%	format('Xn:~d Yn~d',[Xn,Yn]),
	depth_search(Bd,[Xn,Yn],RestArea).

% list up all possible rectangle
%  which include (X1,Y1), (X2,Y2)
% value returned as -topleft coordinates
%   ([+X1,+Y1],[+X2,+Y2],[+Width,+Height],[-RetLeft,-RetTop])
topleft_of_rct_including_2_pts([X1,Y1],[X2,Y2],[Width,Height],
						[RetLeft,RetTop]):-
	get_top_left_right_bottom([X1,Y1],[X2,Y2],[Top,Left,Right,Bottom]),
	Xmin is Right - Width + 1,
	Ymin is Bottom - Height + 1,
	Xmax is Left,
	Ymax is Top,
	gvar(bd_width,BdWidth),
	gvar(bd_height,BdHeight),
	between(Ymin,Ymax,RetTop),
	1 =< RetTop, RetTop =< BdHeight,
	between(Xmin,Xmax,RetLeft),
	1 =< RetLeft, RetLeft =< BdWidth.

% get [top,left,right,bottom] of rect
get_top_left_right_bottom([X1,Y1],[X2,Y2],[Top,Left,Right,Bottom]):-
	( (X1 < X2)->(Left is X1,Right is X2);(Left is X2, Right is X1)),
	( (Y1 < Y2)->(Top is Y1,Bottom is Y2);(Top is Y2, Bottom is Y1)).

% check solved
next_xy(Bd,[Xc,Yc],_):-
	gvar(bd_height,BdHeight),
	Yc == BdHeight,
	gvar(bd_width,BdWidth),

	(
	    (	BdHeight mod 2 == 0  ) ->
	    (	Xc == 1  );
	    (	Xc == BdWidth)
	),
	write('solved'),nl,
	print_bd(Bd),
	abort.

next_xy(Bd,[Xc,Yc],[Xn,Yn]):-
	gvar(bd_width,BdWidth),
	(   (Xc == BdWidth)->
	       (  Xtmp is 1, Ytmp is Yc + 1 );
	       (  Xtmp is Xc + 1, Ytmp is Yc)
	),
	arg(Ytmp,Bd,HLine),
	arg(Xtmp,HLine,Val),
	var(Val),
	Xn is Xtmp,Yn is Ytmp,
	!.

next_xy(Bd,[Xc,Yc],[Xn,Yn]):-
	!,
	gvar(bd_width,BdWidth),
	(   (Xc == BdWidth)->
	       (  Xtmp is 1, Ytmp is Yc + 1 );
	       (  Xtmp is Xc + 1, Ytmp is Yc)
	),
	next_xy(Bd,[Xtmp,Ytmp],[Xn,Yn]).

% initial Bd -> Area List (id,area,x,y)
bd2areaLst(Bd,OutAreaLst):-
	set_gvar(cur_area_id,1),
	set_gvar(area_lst,[]),
	gvar(bd_width,BdWidth),
	gvar(bd_height,BdHeight),
	YMax is BdHeight,
	XMax is BdWidth,
	between(1,YMax,Yc),
	  between(1,XMax,Xc),
	     arg(Yc,Bd,HLine),
	     arg(Xc,HLine,Val),
	     nonvar(Val),
	     gvar(cur_area_id,AreaID),
	     NewAreaID is AreaID + 1,
	     set_gvar(cur_area_id,NewAreaID),
	     gvar(area_lst,AreaLst),
	     set_gvar(area_lst,[[AreaID,Val,Xc,Yc]|AreaLst]),
	  Xc >= BdWidth,  % force backtrack
	Yc >= BdHeight, % force backtrack
	gvar(area_lst,OutAreaLst).
bd2areaLst(_,OutAreaLst):-
	gvar(area_lst,OutAreaLst).

set_rect(Bd,[Top,Left,Width,Height],Val):-
	Yc is Top,
	YEnd is Top + Height - 1,
	set_rect_sub(Bd,[Left,Width],Yc,YEnd,Val).

set_rect_sub(_,_,Yc,YEnd,_):-
	Yc > YEnd ,!.
set_rect_sub(Bd,[Left,Width],Yc,YEnd,Val):-
	Xc is Left,
	arg(Yc,Bd,HLine),
	XEnd is Left + Width - 1,
	set_rect_hline(HLine,Xc,XEnd,Val),
	Yn is Yc + 1,
	set_rect_sub(Bd,[Left,Width],Yn,YEnd,Val).

set_rect_hline(_,Xc,XEnd,_):-
	Xc > XEnd,!.
set_rect_hline(HLine,Xc,XEnd,Val):-
	arg(Xc,HLine,Square),
	Square = Val,
	Xn is Xc + 1,
	set_rect_hline(HLine,Xn,XEnd,Val).

print_bd(Bd):-
	gvar(bd_width,BdWidth),
	gvar(bd_height,BdHeight),

	between(1,BdHeight,Yc),
	  arg(Yc,Bd,HLine),
	  between(1,BdWidth,Xc),
	     arg(Xc,HLine,Val),
	     (	 var(Val)->writef('  .') ; writef('%4r',[Val]) ),
	  Xc == BdWidth,
	  nl,
	Yc == BdHeight,
	true.