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: * MiniZinc: http://www.hakank.org/minizinc/langford2.mzn * Comet : http://www.hakank.org/comet/langford.co * Gecode/R: http://www.hakank.org/gecode_r/langford.rb 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 )]). |