/*

Set partition problem in B-Prolog.

Problem formulation from
http://www.koalog.com/resources/samples/PartitionProblem.java.html
"""
This is a partition problem.
Given the set S = {1, 2, ..., n},
it consists in finding two sets A and B such that:
<ul>
<li>A U B = S,</li>
<li>|A| = |B|,</li>
<li>sum(A) = sum(B),</li>
<li>sum_squares(A) = sum_squares(B).</li>
</ul>
"""

This model just implementa a two set version.

Model created by Hakan Kjellerstrand, hakank@gmail.com

*/

% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/

% find all (7) solutions for N = 16.
go :-
findall(Sets,set_partition(16, Sets),L),
length(L,Len),
format("It was ~d solutions.\n", [Len]).

go2 :-
N :: 2..50,
indomain(N),
once(set_partition(N, _Sets)),
nl,fail.

set_partition(N,Sets) :-

writeln('\nN':N),

(N mod 2 > 0 -> format("~d is not a multiple of 2.\n", [N]), fail ; true ),
(N mod 4 > 0 -> format("~d is not a multiple of 4.\n", [N]), fail ; true ),

N2 is N //2,

[A,B] :: {}..{1..N},
Sets = [A,B],

% same cardinality
#A #= N2,
#A #= #B,

% A and B are disjoint
A #<> B,

% Symmetry breaking: 1 is in the A set
1 #<- A,

% All numbers 1..N must be in some set
foreach(I in 1..N, (I #<- A ; I #<- B)),

% It seems that we must have the labeling
indomain(A),
indomain(B),

set_to_list(A,AList),
set_to_list(B,BList),

% sum of the sets must be equal
ASum #= sum(AList),
BSum #= sum(BList),
ASum #= BSum,

% sum of the squares must be equal
ASumSquared #= sum([ T**2 : I in 1..AList^length, [T], T @= AList[I]]),
BSumSquared #= sum([ T**2 : I in 1..BList^length, [T], T @= BList[I]]),

ASumSquared #= BSumSquared,

% labeling([ASum,BSum,ASumSquared,BSumSquared]),

writeln(A),
writeln(B),
writeln(sums:[ASum,BSum]),
writeln(sumSquares:[ASumSquared,BSumSquared]),
nl.