1. CSPlib
  2. Problems
  3. prob024
  4. Models
  5. langford_bp.pl

024: Langford's number problem

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
/*
 
  Langford's number problem in B-Prolog.
 
  Langford's number problem (CSP lib problem 24)
  http://www.csplib.org/prob/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
  See also my B-Prolog page: http://www.hakank.org/bprolog/
 
*/
 
% 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]).