/*

Langford's number problem in B-Prolog.

Langford's number problem (CSP lib problem 24)
http://www.csplib.org/Problems/prob024/
"""
Arrange 2 sets of positive integers 1..k to a sequence,
such that, following the first occurence of an integer i,
each subsequent occurrence of i, appears i+1 indices later
than the last.
For example, for k=4, a solution would be 41312432
"""

* John E. Miller: Langford's Problem
http://www.lclark.edu/~miller/langford.html

* Encyclopedia of Integer Sequences for the number of solutions for each k
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=014552

Note: For k=4 there are two different solutions:
solution:[4,1,3,1,2,4,3,2]
position:[2,5,3,1,4,8,7,6]
and
solution:[2,3,4,2,1,3,1,4]
position:[5,1,2,3,7,4,6,8]

Which this symmetry breaking

Solution[1] #< Solution[K2],

then just the second solution is shown.

Model created by Hakan Kjellerstrand, hakank@gmail.com

*/

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

%
% Find all solutions for K=2..8.
%
go :-
Selection = ff,
Choice = down,
foreach(K in 2..8,
[L,Len],
(
writeln(k:K),
time(findall([K,Backtracks,Solution,Position], langford(K,Solution,Position,Selection,Choice,Backtracks), L)),
length(L,Len),
foreach(LL in L,
[_K, Backtracks,Solution,Position],
(
[K,Backtracks,Solution,Position] = LL,
writeln(solution:Solution),
writeln(position:Position),
writeln(backtracks:Backtracks),
nl
)
),
writeln(len:Len),
nl
)
).

%
% For a specific K, check all possible variants of Selection and
% Choice methods.
% This was originally to check which heuristics that was the best.
% However, all heuristics give 0 backtracks and about 0.43 seconds.
%
go2 :-
K = 8,
selection(Selections),
choice(Choices),
writeln(k:K),
foreach(Selection in Selections, Choice in Choices,
[Backtracks,Solution,Position,L,Len],
(
writeln([selection:Selection, choice:Choice]),
time(findall(Backtracks,
langford(K,Solution,Position,Selection,Choice,Backtracks),
L)),
length(L,Len),
format('All backtracks: ~q\n', [L]),
writeln(len:Len),
nl,
flush_output
)
).

%
% Just get the first (if any) solutions for K in 2..12
%
go3 :-
foreach(K in 2..12,
[Solution,Position,Backtracks],
(
writeln(k:K),
time(langford(K,Solution,Position,ff,down,Backtracks)) ->
writeln(solution:Solution),
writeln(position:Position),
writeln(backtracks:Backtracks),
nl
;
writeln('No solution'),
nl,
true

)
).

langford(K, Solution, Position) :-
langford(K, Solution, ff, down, Position,_Backtracks).

langford(K, Solution, Position,Selection,Choice,Backtracks) :-
statistics(backtracks,Backtracks1),

K2 is 2*K,
length(Position, K2),
Position :: 1..K2,

length(Solution,K2),
Solution :: 1..K,

alldifferent(Position),

% symmetry breaking:
Solution[1] #< Solution[K2],
% Solution[1] #> Solution[K2],

foreach(I in 1..K,
[IK,PositionI,PositionIK,SolutionPositionI,SolutionPositionIK],
(
IK is I+K,
nth1(IK, Position, PositionIK),
nth1(I, Position, PositionI),
% I1 is I+1,
PositionIK #= PositionI + I+1,
nth1(PositionI,Solution,SolutionPositionI),
SolutionPositionI #= I,
nth1(PositionIK,Solution,SolutionPositionIK),
SolutionPositionIK #= I
)
),

term_variables([Position,Solution], Vars),
labeling([Selection,Choice], Vars),

statistics(backtracks,Backtracks2),
Backtracks is Backtracks2 - Backtracks1.

% Variable selection
selection([backward,constr,degree,ff,ffc,forward,inout,leftmost,max,min]).

% Value selection
choice([down,updown,split,reverse_split]).