Download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/*
 
  Langford's number problem in ECLiPSe.
 
 
  Langford's number problem (CSP lib problem 24)
  """
  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
  
 
  Also, see the following models:
 
 
 
  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my ECLiPSe page: http://www.hakank.org/eclipse/
 
*/
 
% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
 
:-lib(ic).
:-lib(ic_global).
:-lib(ic_search).
%:-lib(branch_and_bound).
:-lib(listut).
:-lib(util). % for time
%:-lib(propia).
 
 
 
go :-
        K :: 2..8,
        indomain(K),
        writeln(K),
        Selection = first_fail,
        Choice = indomain_min,
        writeln([selection:Selection, choice:Choice]),
        time(findall([K,Backtracks,Solution,Position], langford(K,Solution,Position,Selection,Choice,Backtracks),
                L)),       
        length(L,Len),
        writeln(L),
        writeln(len:Len),
        nl,fail.
 
 
% For a specific K, check all possible variants of Selection and
% Choice methods.
go2 :-
        K = 8,
        selection(Selections),
        choice(Choices),
        writeln(K),
        ( foreach(Selection,Selections), param(Choices,K) do
              ( foreach(Choice, Choices),
                param(K,Selection) do
                   writeln([selection:Selection, choice:Choice]),
                   time(findall(Backtracks,
                                langford(K,_Solution,_Position,Selection,Choice,Backtracks),
                                L)),
                   length(L,Len),
                   writeln(backtracks:L),
                   writeln(len:Len),
                   nl,
                   flush(output)
              )
        ).
         
 
selection([input_order,first_fail, anti_first_fail, smallest,largest,
           occurrence,most_constrained,max_regret]).
choice([indomain,indomain_min,indomain_max,indomain_middle,
         indomain_median,indomain_split, indomain_random,
         indomain_interval]).
 
         
langford(K, Solution, Position) :-
        langford(K, Solution, Position,first_fail,indomain,_Backtracks).
 
 
langford(K, Solution, Position,Selection,Choice,Backtracks) :-
        K2 is 2*K,
        length(Position, K2),
        Position :: 1..K2,
 
        length(Solution,K2),
        Solution :: 1..K,
 
        ic_global:alldifferent(Position),
 
        %  symmetry breaking
        nth1(1,Solution,Solution1),
        nth1(K2,Solution,SolutionK2),
        Solution1 #< SolutionK2,
 
 
        ( for(I,1,K), param(Position,Solution,K) do
              IK is I+K,
              nth1(IK, Position, PositionIK),
              nth1(I, Position, PositionI),
              I1 is I+1,
              PositionIK #= PositionI + I1,
              nth1(PositionI,Solution,SolutionPositionI),
              SolutionPositionI #= I,
              nth1(PositionIK,Solution,SolutionPositionIK),
              SolutionPositionIK #= I
        ),
 
 
        term_variables([Position,Solution], Vars),
        search(Vars,0,Selection,Choice,complete,[backtrack(Backtracks)]).