% From Alain Colmerauer: An Introduction to Prolog III,
% Communications of the ACM, 33(7), 69-90, 1990.

:- use_module(library(clpq), [{}/1]).

% ------------------------------------------------------------
% The original program
% ------------------------------------------------------------

% Rectangle 1 x Width is covered by distinct squares of size Ss.
filled_rectangle(Width, Ss) :-
  distinct_squares(Ss), { Width >= 1 }, 
  filled_hole([-1,Width,1], _, Ss, []).

% distinct_squares(Ss): All elements of Ss are distinct.
distinct_squares([]).
distinct_squares([S|Ss]) :-
  { S > 0 }, outof(Ss, S), distinct_squares(Ss).

outof([],     _).
outof([S|Ss], S0) :- { S =\= S0 }, outof(Ss, S0).

% filled_hole(L0, L, Ss0, Ss): Hole in line L0
% filled with squares Ss0-Ss (diff list) gives line L.
% Def: h(L): sum of lengths of vertical lines in L.
% Pre: All elements of L0 except the first >= 0.
% Post: All elems in L >=0, h(L0) = h(L).
filled_hole(L, L, Ss, Ss) :-
  L = [V|_], {V >= 0}.
filled_hole([V|HL], L, [S|Ss0], Ss) :-
  { V < 0 }, placed_square(S, HL, L1),
  filled_hole(L1, L2, Ss0, Ss1), { V1=V+S },
  filled_hole([V1,S|L2], L, Ss1, Ss).

% placed_square(S, HL, L): placing a square on
% HL horizontal line gives (vertical) line L.
% Pre: all elems in HL >=0
% Post: all in L except first >=0, h(L) = h(HL)-S.
placed_square(S, [H,V,H1|L], L1) :- { S > H, V=0, H2=H+H1 }, 
  placed_square(S, [H2|L], L1).
placed_square(S, [S,V|L], [X|L]) :- { X=V-S }.
placed_square(S, [H|L], [X,Y|L]) :- { S < H, X= -S, Y=H-S }.


% ------------------------------------------------------------
% An example to illustrate the first solution for N = 9
% ------------------------------------------------------------
/*
|------------------|-------------------|----------------------------|
|                  |                   |                            |
|                  |                   |                            |
|                  |                   |                            |
|      S9 = 9      |                   |                            |
|                  |      S8 = 10      |                            |
|                  |                   |                            |
|                  |                   |          S6 = 14           |
|                  |                   |                            |
|----------------|-|                   |                            |
|                |-|-----------|-------|                            |
|                |             |       |                            |
|                |             | S5=4  |                            |
|     S3 = 8     |    S4=7     |       |                            |
|                |             |-------|----------------------------|
|                |             |                                    |
|                |             |                                    |
|----------------|-------------|                                    |
|                              |                                    |
|                              |                                    |
|                              |                                    |
|                              |                                    |
|                              |               S2 = 18              |
|                              |                                    |
|          S1 = 15             |                                    |
|                              |                                    |
|                              |                                    |
|                              |                                    |
|                              |                                    |
|                              |                                    |
|                              |                                    |
|                              |                                    |
|------------------------------|------------------------------------|
( Note: S7 = 1)
*/
:- public filled_rectangle9_sol1/2, filled_rectangle9_sol1_bis/2.
% A minimal subset of the constraints generated by the above 
% program, able to find the first solution for N = 9.
filled_rectangle9_sol1(Width, Ss) :-
        Ss = [S1,S2,S3,S4,S5,S6,S7,S8,S9],
%       distinct_squares(Ss), {Width>=1},
        {S1+S2=Width},
%       {S1=<S2},               
        {S3+S4=S1},                      {S6>=S5+S8},  
        {S5+S6=S2},		         {S4+S7=S3},   
        {S2+S6=<1},		         {S9=S3+S7},   
        {S2+S5=S1+S4},		         {S8>=S7+S9},  
        {S7+S8=S4+S5},		         {S1+S3+S9>=1}.

% A variant of the above, replacing less-eq and greater-eq 
% by equality --- one more constraint can be eliminated.
filled_rectangle9_sol1_bis(Width, [S1,S2,S3,S4,S5,S6,S7,S8,S9]) :-
        {S1+S2=Width},
        {S3+S4=S1},
        {S5+S6=S2},
        {S2+S6=1},     %
%       {S2+S5=S1+S4}, %
        {S7+S8=S4+S5},
        {S6=S5+S8},    %
        {S4+S7=S3},    %
        {S9=S3+S7},
        {S8=S7+S9},    %
        {S1+S3+S9=1}.  %

% ------------------------------------------------------------
% A variant of the filled_rectangle predicate
% capable of building a trail and collecting constraints.
% ------------------------------------------------------------


:- use_module(library(lists), [append/3,member/2,nth/3]).

% Rectangle 1 x Width is covered by
% distinct squares of size Ss.
% Execute this predicate according to the
% Opts option list:
% eqsq --- squares of equal size are allowed
% trail(?Trail) --- return in Trail a list of atoms
%       describing the choices made
% collect(+Trail, ?Constraints) --- follow the execution
%       path described by Trail and return the list of
%       constraints posted on that path.
filled_rectangle(Width, Ss, Opts) :-
        (   member(collect(Trail,Cs), Opts) ->
            Mode = collect, L0 = Trail/Cs, L = []/[]
        ;   member(trail(Trail), Opts) ->
            Mode = trail, L0 = Trail, L = []
        ;   Mode = normal, L0 = [], L = []
        ),
        (   member(eqsq, Opts) -> EqSq = true
        ;   EqSq = false
        ),
        filled_rectangle(Width, Ss, Mode, EqSq, L0, L).

filled_rectangle(Width, Ss, Mode, EqSq) -->
        distinct_squares(Ss, Mode, EqSq),
        exec(Mode, [ Width >= 1]),
        (   {Mode = normal} -> { filled_hole([-1,Width,1], _, Ss, []) }
        ;   filled_hole([-1,Width,1], _, Ss, [], Mode)
        ).

% distinct_squares(Ss): All elements of Ss are
% positive and distinct. 
distinct_squares([], _, _) --> [].
distinct_squares([S|Ss], Mode, EqSq)  -->
        exec(Mode, [ S > 0 ]),
        (   {EqSq = true} -> {true}
        ;   outof(Ss, S, Mode)
        ),
        distinct_squares(Ss, Mode, EqSq).

outof([],      _, _) --> [].
outof([S|Ss], S0, Mode)  -->
        exec(Mode, [ S =\= S0 ]),
        outof(Ss, S0, Mode).

% filled_hole(L0, L, Ss0, Ss): Hole in line L0
% filled with squares Ss0-Ss (diff list) gives line L.
filled_hole(L, L, Ss, Ss, Mode) --> 
  {L = [V|_]}, exec(Mode, nohl, [ V >= 0 ]).
filled_hole([V|HL], L, [S|Ss0], Ss, Mode) --> 
  exec(Mode, hole, [ V < 0 ]), placed_square(S, HL, L1, Mode),
  filled_hole(L1, L2, Ss0, Ss1, Mode), exec(Mode, [ V1=V+S ]),
  filled_hole([V1,S|L2], L, Ss1, Ss, Mode).

% placed_square(S, HL, L): placing a square on
% HL horizontal line gives (vertical) line L.
placed_square(S, [H,V,H1|L], L1, Mode) --> 
  exec(Mode, join,  [ S > H, V=0, H2=H+H1 ]), 
  placed_square(S, [H2|L], L1, Mode).
placed_square(S, [H,V|L], [X|L], Mode) --> 
  exec(Mode, exct, [ H = S, X=V-S ]).
placed_square(S, [H|L], [X,Y|L], Mode) --> 
  exec(Mode, part, [ S < H, X= -S, Y=H-S ]).

% exec(Mode, Trail, Constraints, A0, A): Execute the
% Constraints list in Mode, adding Trail to the trail,
% if needed. The form of the accumulator pair A0-A depends
% on the execution mode:
%   normal  --- irrelevant
%   trail   --- a list of elements to be trailed
%   collect --- a pair of lists TrailElems/Constraints 
exec(normal, _, C) -->
  {constrain_list(C)}.
exec(trail, T, C) -->
  [T], {constrain_list(C)}.
exec(collect, T, C, Trl0/Cns0, Trl/Cns) :-
  Trl0 = [T|Trl], append(C, Cns, Cns0).

% A variant of exec/5 without trailing.
exec(normal, C) -->
  {constrain_list(C)}.
exec(trail, C) -->
  {constrain_list(C)}.
exec(collect, C, Trl/Cns0, Trl/Cns) :-
  append(C, Cns, Cns0).

% constrain_list(L): post all clpq constraints in list L.
constrain_list([]).
constrain_list([C|Cs]) :-
        {C}, constrain_list(Cs).

:- public test/4, test/5.

% Tests of the program, with timing
test(N, MSec, Width, Ss) :-
	test(N, MSec, Width, Ss, []).

test(N, MSec, Width, Ss, Opts) :-
  length(Ss, N), N > 1, statistics(runtime, _),
  filled_rectangle(Width, Ss, Opts), 
  statistics(runtime, [_,MSec]).


:- public test2/3.

% Find first solution for N with Opts, and output a clause
% containing all constraints generated for this solution.
test2(N, Opts, Clause) :-
  length(_Ss, N), N > 1, 
  filled_rectangle(_Width, _Ss, [trail(T)|Opts]), 
  length(Ss, N), N > 1, 
  filled_rectangle(Width, Ss, [collect(T,C0)|Opts]),
  name_variables(Width, Ss),
  transform_constraints(C0, C, []),
  list_to_round_list(C, C1),
  Clause = (filled_rectangle1(Width, Ss) :- C1).

% Instantiate the given variables  (Width and elements of Ss)
% with their names.
name_variables(Width, Ss) :-
        Width = '$VAR'("Width"),
        name_sq_variables(Ss, 1).

name_sq_variables([], _).
name_sq_variables([S|Ss], N) :-
        number_codes(N, NCs),
        S = '$VAR'([0'S|NCs]),  
        N1 is N+1,
        name_sq_variables(Ss, N1).

% transform_constraints(Cs, L0, L):
% L0-L is a simplified form of constraint list Cs.
transform_constraints([X=Y|Cs]) -->
        {X=Y}, !, transform_constraints(Cs).
transform_constraints([C0|Cs]) -->
        {simplify(C0, C)}, [{C}],
        transform_constraints(Cs).
transform_constraints([]) --> [].

% C is the simplified form of C0.
simplify(C0, C) :-
        C0 =.. [Op,L,R],
        pos_neg(L-R, Pos, [], Neg, []), 
        list_to_sum(Pos, P),
        list_to_sum(Neg, N),
        compose(P, Op, N, C), !.
simplify(C, C).

% C is the Prolog term describing the constraint L Op R.
compose(L, Op, R, C) :-
        number(L), \+ number(R), !, reversed_op(Op, OOp),
        compose(R, OOp, L, C).
compose(L, Op, R, C) :-
        C =.. [Op,L,R].

reversed_op(<, >).
reversed_op(=<, >=).
reversed_op(>, <).
reversed_op(>=, =<).
reversed_op(=, =).
reversed_op(=\=, =\=).

% pos_neg(Term, P0, P, N0, N): term Term is equivalent
% to (X1+...+Xn)-(Y1+...+Ym) where P0-P = [X1,...,Xn]
% and N0-N = [Y1,...,Yn].
pos_neg(A+B, P0, P, N0, N) :- !,
        pos_neg(A, P0, P1, N0, N1),
        pos_neg(B, P1, P, N1, N).
pos_neg(A-B, P0, P, N0, N) :- !,
        pos_neg(A, P0, P1, N0, N1),
        pos_neg(B, N1, N, P1, P).
pos_neg(-A, P0, P, N0, N) :- !,
        pos_neg(A, N0, N, P0, P).
pos_neg(0, P, P0, N, N0) :- !,
        P = P0, N = N0.
pos_neg(I, P, P0, N, N0) :-
        number(I), I < 0, !, I1 is -I,
        N = [I1|N0], P = P0.
pos_neg(A, [A|P0], P0, N0, N0).


% show_rect(Width, Ss, Magnify): Display rectangle tiling
% characterised by Width and Ss. The smallest square will be
% displayed using size Magnify.
show_rect(Width, Ss, Magnify) :-
	smallest(Ss, Smallest),
	Smallest = rat(_,M),
	Magnify1 is Magnify*M,
	{H0 = 1*Magnify1},
	{W0 = Width*Magnify1},
	H0 = rat(H,1),
	W0 = rat(W,1),
	matrix_of_vars(H, W, Mx),
	{X = 0, Y = 0},
	fill_matrix([-1,Width,1], _, Ss, [], st(X, Y, 0'1, Mx, H), _),
	show_matrix(Mx).

% fill_matrix(L0, L, Ss0, S, St0, St):
% Simulate filled_hole(L0, L, Ss0, S) and fill squares in the matrix
% stored in state St0, returning state St.
% States are of form st(X, Y, Fill, Mx, H), where
%    (X, Y) are the starting coordinates of line L0
%    Fill is the char code to be used for filling the next square
%    Mx is the matrix in which the squares are filled in
%    H is the height of Mx
fill_matrix(L, L, Ss0, Ss0, St, St) :-
	L = [V|_], {V >= 0}.
fill_matrix([V|HL], L, [S|Ss0], Ss, St0, St) :-
	{ V < 0 },
	placed_square(S, HL, L1),
	fill_square(V, S, St0, St1),
	fill_matrix(L1, L2, Ss0, Ss1, St1, St2),
	{ V1=V+S },
	new_state(St0, St2, St3),
	fill_matrix([V1,S|L2], L, Ss1, Ss, St3, St).

% matrix(St, Mx, H): State St contains matrix Mx and height H 
matrix(st(_X, _Y, _Fill, Mx, H), Mx, H).

% filler(St, Fill): State St contains filler Fill
filler(st(_X, _Y, Fill, _Mx, _H), Fill).

% position(St, X, Y): State St contains coordinates X and Y.
position(st(X, Y, _Fill, _Mx, _H), X, Y).

% Having placed_square of size S on a line [V|_],
% fill the appropriate square in state St0, resulting
% in state St1.
fill_square(V, S, St0, St1) :-
	matrix(St0, Mx, H),
	matrix(St1, Mx, H),
	filler(St0, Fill),
	next_filler(Fill, Fill1),
	filler(St1, Fill1),
	position(St0, X0, Y0),
	{X1 = X0+S,
	 Y1 = Y0+V+S},
	position(St1, X1, Y1),
	fill_square(X0, Y1, S, Fill, H, Mx).

% Having placed_square in state St0, and subsequently filled_hole
% resulting in state St1, the initial state of the subsequent
% filled_hole is St.
new_state(St0, St1, St) :-
	position(St0, X, Y),
	position(St, X, Y),
	matrix(St1, Mx, H),
	matrix(St, Mx, H),
	filler(St1, Fill),
	filler(St, Fill).

% Fill a square with top left corner coordinates  (X,Y)
% and size Size, using filler Fill in matrix MX of height H.
fill_square(X, Y, Size, Fill, H, Mx) :-
	{R0 = -Y*H +1},
	{C0 = X*H+1},
	R0 = rat(R,1),
	C0 = rat(C,1),
	{S0 = Size*H},
	S0 = rat(S,1),
	draw_square(R, C, S, Fill, Mx).

% Fill a square with top left corner in row R column C, size S
% using filler Fill  in matrix Mx
draw_square(R, C, S, Fill, Mx) :-
	fill_row_slice(R, C, S, Fill, Mx),
	LastR is R+S-1,
	fill_row_slice(LastR, C, S, Fill, Mx),
	fill_col_slice(R, C, S, Fill, Mx),
	LastC is C+S-1,
	fill_col_slice(R, LastC, S, Fill, Mx).

% All elements of a single row slice of matrix Mx which 
% starts at row R0 column C0, and has width S0 are equal to Fill.
fill_row_slice(R0, C0, S0, Fill, Mx) :-
	(   S0 =:= 0 -> true
	;   matrix_elem(R0, C0, Mx, Fill),
	    C1 is C0+1, S1 is S0-1,
	    fill_row_slice(R0, C1, S1, Fill, Mx)
	).

% All elements of a single column slice of matrix Mx which 
% starts at row R0 column C0, and has height S0 are equal to Fill.
fill_col_slice(R0, C0, S0, Fill, Mx) :-
	(   S0 =:= 0 -> true
	;   matrix_elem(R0, C0, Mx, Fill),
	    R1 is R0+1, S1 is S0-1,
	    fill_col_slice(R1, C0, S1, Fill, Mx)
	).

% Fill is the next filler character code to be used after Fill0.
next_filler(Fill0, Fill) :-
	(   Fill0 =:= 0'9 -> Fill = 0'A
	;   Fill is Fill0+1
	).

% Display matrix Mx.
show_matrix(Mx) :-
	(   member(Row, Mx),
	    (   member(Elem, Row),
		(   nonvar(Elem) -> put_code(Elem), put_code(0' )
		;   write('  ')
		),
		fail
	    ;   nl
	    ),
	    fail
	;   true
	).


% ------------------------------------------------------------
% Utilities
% ------------------------------------------------------------
        

% list_to_round_list(+L, ?RL) :- "Round" list RL contains
% the same elements as list L
% (i.e. if L = [A,B,...,X] then RL = (A,B,...,X) ).
list_to_round_list([X|L], RL) :-
        list_to_round_list(L, X, RL).

list_to_round_list([], X, X).
list_to_round_list([Y|L], X, (X,RL)) :-
        list_to_round_list(L, Y, RL).

% list_to_sum(L, S): S = X1+X2+...Xn, where L = [X1,X2,...,Xn]
list_to_sum([], 0).
list_to_sum([A|L], S) :-
        list_to_sum(L, A, S).

list_to_sum([], S, S).
list_to_sum([A|L], S0, S) :-
        list_to_sum(L, S0+A, S).

% Matrix is a matrix of size RowNum x ClmNum, with all elements uninstantiated.
% :- pred matrix_of_vars(int::in, int::in, matrix(T)::out).
matrix_of_vars(0, _ClmNum, []) :- !.
matrix_of_vars(RowNum, ClmNum, [Row|Rows]) :-
	length(Row, ClmNum),
	RowNum1 is RowNum-1,
	matrix_of_vars(RowNum1, ClmNum, Rows).

% matrix_elem(I, J, M, E): E is the element of matrix M in row I, column J.
% :- pred matrix_elem(int::in, int::in, matrix(T)::in, T::out).
matrix_elem(RowI, ClmI, Matrix, Elem) :-
        nth(RowI, Matrix, Row),
        nth(ClmI, Row, Elem).

% smallest(L, Min): Min is the minimal element of L
% Nonempty list L consists of clpq/clpr numbers.
smallest([S], S) :- !.
smallest([S|Ss], Min) :-
	smallest(Ss, Min0),
	{Min = min(S, Min0)}.
 


end_of_file.

% ------------------------------------------------------------
% Sample runs (Pentium III, 600 MHz)
% ------------------------------------------------------------

| ?- test(N, MSec, Width, Ss).

N = 9,
Ss = [15/32,9/16,1/4,7/32,1/8,7/16,1/32,5/16,9/32],
MSec = 8090,
Width = 33/32 ? ;

N = 9,
Ss = [33/61,36/61,28/61,5/61,2/61,9/61,25/61,7/61,16/61],
MSec = 1000,
Width = 69/61 ? ;

N = 9,
Ss = [9/16,15/32,7/32,1/4,7/16,1/8,5/16,1/32,9/32],
MSec = 10840,
Width = 33/32 ? 

yes
| ?- test(10, MSec, Width, Ss).

Ss = [45/104,15/26,1/4,19/104,2/13,11/26,7/104,3/26,33/104,7/26],
MSec = 35770,
Width = 105/104 ? ;

Ss = [55/94,30/47,39/94,8/47,11/94,15/94,17/47,23/94,2/47,19/94],
MSec = 4300,
Width = 115/94 ? ;

Ss = [27/55,6/11,13/55,1/5,3/55,8/55,5/11,2/55,17/55,3/11],
MSec = 14500,
Width = 57/55 ? 

yes
| ?- test(_N, _MSec, Width, Ss, [eqsq]).

Ss = [1,1],
Width = 2 ? ;

Ss = [1/2,1,1/2],
Width = 3/2 ? ;

Ss = [1,1/2,1/2],
Width = 3/2 ? ;

Ss = [1,1,1],
Width = 3 ? ;

Ss = [1/3,1,1/3,1/3],
Width = 4/3 ? ;

Ss = [1/2,1/2,1/2,1/2],
Width = 1 ? ;

Ss = [2/3,1,1/3,1/3],
Width = 5/3 ? ;

Ss = [1,1/3,1/3,1/3],
Width = 4/3 ? ;

Ss = [1,2/3,1/3,1/3],
Width = 5/3 ? ;

Ss = [1/3,1/3,1,2/3],
Width = 5/3 ? ;

Ss = [1/2,1,1,1/2],
Width = 5/2 ? ;

Ss = [1,1/3,1/3,2/3],
Width = 5/3 ? ;

Ss = [1,1/2,1,1/2],
Width = 5/2 ? ;

Ss = [1,1,1/2,1/2],
Width = 5/2 ? ;

Ss = [1,1,1,1],
Width = 4 ? ;

Ss = [1/4,1,1/4,1/4,1/4],
Width = 5/4 ? 

yes
| ?- test2(4, [eqsq], Clause), portray_clause(Clause).
filled_rectangle1(Width, [S1,S2,S3,S4]) :-
        {S1>0},
        {S2>0},
        {S3>0},
        {S4>0},
        {Width>=1},
        {0<1},
        {S1<Width},
        {S1>0},
        {Width=S1+S2},
        {S2=<1},
        {S2>=S1},
        {S1<1},
        {S1=S3},
        {S2>=S1+S3},
        {S1+S3<1},
        {S3=S4},
        {S2>=S1+S3+S4},
        {S1+S3+S4>=1}.

Clause = filled_rectangle1(Width,[S1,S2,S3,S4]):-{S1>0},{S2>0},{S3>0},{S4>0},{Width>=1},{0<1},{S1<Width},{...},...,... ? 

yes
| ?- test2(9, [], Clause), portray_clause(Clause).
filled_rectangle1(Width, [S1,S2,S3,S4,S5,S6,S7,S8,S9]) :-
        {S1>0},
        {S2=\=S1},
        {S3=\=S1},
        {S4=\=S1},
        {S5=\=S1},
        {S6=\=S1},
        {S7=\=S1},
        {S8=\=S1},
        {S9=\=S1},
        {S2>0},
        {S3=\=S2},
        {S4=\=S2},
        {S5=\=S2},
        {S6=\=S2},
        {S7=\=S2},
        {S8=\=S2},
        {S9=\=S2},
        {S3>0},
        {S4=\=S3},
        {S5=\=S3},
        {S6=\=S3},
        {S7=\=S3},
        {S8=\=S3},
        {S9=\=S3},
        {S4>0},
        {S5=\=S4},
        {S6=\=S4},
        {S7=\=S4},
        {S8=\=S4},
        {S9=\=S4},
        {S5>0},
        {S6=\=S5},
        {S7=\=S5},
        {S8=\=S5},
        {S9=\=S5},
        {S6>0},
        {S7=\=S6},
        {S8=\=S6},
        {S9=\=S6},
        {S7>0},
        {S8=\=S7},
        {S9=\=S7},
        {S8>0},
        {S9=\=S8},
        {S9>0},
        {Width>=1},
        {0<1},
        {S1<Width},
        {S1>0},
        {Width=S1+S2},
        {S2=<1},
        {S2>=S1},
        {S1<1},
        {S3<S1},
        {S3>0},
        {S1=S3+S4},
        {S2<S1+S4},
        {S5<S2},
        {S5>0},
        {S2=S5+S6},
        {S2+S6=<1},
        {S6>=S5},
        {S2+S5>=S1+S4},
        {S4<S3},
        {S7<S4},
        {S7>0},
        {S8+S7>S4},
        {S2+S5=S1+S4},
        {S4+S5=S7+S8},
        {S6>=S5+S8},
        {S8>=S7},
        {S4+S7>=S3},
        {S1+S3<1},
        {S9>S3},
        {S4+S7=S3},
        {S3+S7=S9},
        {S8>=S7+S9},
        {S1+S3+S9>=1}.

Clause = filled_rectangle1(Width,[S1,S2,S3,S4,S5,S6,S7,S8|...]):-{S1>0},{S2=\=S1},{S3=\=S1},{S4=\=S1},{S5=\=S1},{S6=\=S1},{S7=\=S1},{...},...,... ? 

yes
| ?- test(3, _, Width, Ss, [eqsq]), show_rect(Width, Ss, 4).
3 3 3 3 2 2 2 2 2 2 2 2 
3     3 2             2 
3     3 2             2 
3 3 3 3 2             2 
1 1 1 1 2             2 
1     1 2             2 
1     1 2             2 
1 1 1 1 2 2 2 2 2 2 2 2 
Ss = [1/2,1,1/2],
Width = 3/2 ? ;
1 1 1 1 1 1 1 1 3 3 3 3 
1             1 3     3 
1             1 3     3 
1             1 3 3 3 3 
1             1 2 2 2 2 
1             1 2     2 
1             1 2     2 
1 1 1 1 1 1 1 1 2 2 2 2 
Ss = [1,1/2,1/2],
Width = 3/2 ? ;
1 1 1 1 2 2 2 2 3 3 3 3 
1     1 2     2 3     3 
1     1 2     2 3     3 
1 1 1 1 2 2 2 2 3 3 3 3 
Ss = [1,1,1],
Width = 3 ? ;
no
| ?- test(4, _, Width, Ss, [eqsq]), show_rect(Width, Ss, 4).
4 4 4 4 2 2 2 2 2 2 2 2 2 2 2 2 
4     4 2                     2 
4     4 2                     2 
4 4 4 4 2                     2 
3 3 3 3 2                     2 
3     3 2                     2 
3     3 2                     2 
3 3 3 3 2                     2 
1 1 1 1 2                     2 
1     1 2                     2 
1     1 2                     2 
1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 
Ss = [1/3,1,1/3,1/3],
Width = 4/3 ? ;
3 3 3 3 4 4 4 4 
3     3 4     4 
3     3 4     4 
3 3 3 3 4 4 4 4 
1 1 1 1 2 2 2 2 
1     1 2     2 
1     1 2     2 
1 1 1 1 2 2 2 2 
Ss = [1/2,1/2,1/2,1/2],
Width = 1 ? ;
3 3 3 3 4 4 4 4 2 2 2 2 2 2 2 2 2 2 2 2 
3     3 4     4 2                     2 
3     3 4     4 2                     2 
3 3 3 3 4 4 4 4 2                     2 
1 1 1 1 1 1 1 1 2                     2 
1             1 2                     2 
1             1 2                     2 
1             1 2                     2 
1             1 2                     2 
1             1 2                     2 
1             1 2                     2 
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 
Ss = [2/3,1,1/3,1/3],
Width = 5/3 ? ;
1 1 1 1 1 1 1 1 1 1 1 1 4 4 4 4 
1                     1 4     4 
1                     1 4     4 
1                     1 4 4 4 4 
1                     1 3 3 3 3 
1                     1 3     3 
1                     1 3     3 
1                     1 3 3 3 3 
1                     1 2 2 2 2 
1                     1 2     2 
1                     1 2     2 
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 
Ss = [1,1/3,1/3,1/3],
Width = 4/3 ? ;
1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 4 4 4 4 
1                     1 3     3 4     4 
1                     1 3     3 4     4 
1                     1 3 3 3 3 4 4 4 4 
1                     1 2 2 2 2 2 2 2 2 
1                     1 2             2 
1                     1 2             2 
1                     1 2             2 
1                     1 2             2 
1                     1 2             2 
1                     1 2             2 
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 
Ss = [1,2/3,1/3,1/3],
Width = 5/3 ? ;
4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 
4             4 3                     3 
4             4 3                     3 
4             4 3                     3 
4             4 3                     3 
4             4 3                     3 
4             4 3                     3 
4 4 4 4 4 4 4 4 3                     3 
1 1 1 1 2 2 2 2 3                     3 
1     1 2     2 3                     3 
1     1 2     2 3                     3 
1 1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 
Ss = [1/3,1/3,1,2/3],
Width = 5/3 ? ;
4 4 4 4 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 
4     4 2             2 3             3 
4     4 2             2 3             3 
4 4 4 4 2             2 3             3 
1 1 1 1 2             2 3             3 
1     1 2             2 3             3 
1     1 2             2 3             3 
1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 
Ss = [1/2,1,1,1/2],
Width = 5/2 ? ;
1 1 1 1 1 1 1 1 1 1 1 1 4 4 4 4 4 4 4 4 
1                     1 4             4 
1                     1 4             4 
1                     1 4             4 
1                     1 4             4 
1                     1 4             4 
1                     1 4             4 
1                     1 4 4 4 4 4 4 4 4 
1                     1 2 2 2 2 3 3 3 3 
1                     1 2     2 3     3 
1                     1 2     2 3     3 
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 3 
Ss = [1,1/3,1/3,2/3],
Width = 5/3 ? ;
1 1 1 1 1 1 1 1 4 4 4 4 3 3 3 3 3 3 3 3 
1             1 4     4 3             3 
1             1 4     4 3             3 
1             1 4 4 4 4 3             3 
1             1 2 2 2 2 3             3 
1             1 2     2 3             3 
1             1 2     2 3             3 
1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 
Ss = [1,1/2,1,1/2],
Width = 5/2 ? ;
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 4 4 4 4 
1             1 2             2 4     4 
1             1 2             2 4     4 
1             1 2             2 4 4 4 4 
1             1 2             2 3 3 3 3 
1             1 2             2 3     3 
1             1 2             2 3     3 
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 
Ss = [1,1,1/2,1/2],
Width = 5/2 ? ;
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 
1     1 2     2 3     3 4     4 
1     1 2     2 3     3 4     4 
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 
Ss = [1,1,1,1],
Width = 4 ? ;
no
| ?- test(9, _, Width, Ss), show_rect(Width, Ss, 1).
9 9 9 9 9 9 9 9 9 8 8 8 8 8 8 8 8 8 8 6 6 6 6 6 6 6 6 6 6 6 6 6 6 
9               9 8                 8 6                         6 
9               9 8                 8 6                         6 
9               9 8                 8 6                         6 
9               9 8                 8 6                         6 
9               9 8                 8 6                         6 
9               9 8                 8 6                         6 
9               9 8                 8 6                         6 
9 9 9 9 9 9 9 9 9 8                 8 6                         6 
3 3 3 3 3 3 3 3 7 8 8 8 8 8 8 8 8 8 8 6                         6 
3             3 4 4 4 4 4 4 4 5 5 5 5 6                         6 
3             3 4           4 5     5 6                         6 
3             3 4           4 5     5 6                         6 
3             3 4           4 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 
3             3 4           4 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 
3             3 4           4 2                                 2 
3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 2                                 2 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2                                 2 
1                           1 2                                 2 
1                           1 2                                 2 
1                           1 2                                 2 
1                           1 2                                 2 
1                           1 2                                 2 
1                           1 2                                 2 
1                           1 2                                 2 
1                           1 2                                 2 
1                           1 2                                 2 
1                           1 2                                 2 
1                           1 2                                 2 
1                           1 2                                 2 
1                           1 2                                 2 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 
Ss = [15/32,9/16,1/4,7/32,1/8,7/16,1/32,5/16,9/32],
Width = 33/32 ? 
yes
| ?- 
