#!/usr/bin/ruby
#
# Langford number's problem in Gecode/R
#
# 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
#
# * MiniZinc model http://www.hakank.org/minizinc/langford2.mzn

#
# Model created by Hakan Kjellerstrand, hakank@bonetmail.com
# See also my Gecode/R page: http://www.hakank.org/gecode_r
#


require 'rubygems'
require 'gecoder'
STDOUT.sync = true


class Langford

  include Gecode::Mixin

  def initialize(k = 4)

    # positions where to place a numbers
    position_is_an int_var_array(k*2+1, 0..2*k)
    # the solution
    x_is_an int_var_array(k*2+1, 0..k)

    position.must_be.distinct

    # "Channel" between the positions and the solution.
    # The first 1..k positions is where to put the first number (in the pair)
    # The second k+1..2*k where to put the second number.
    (1..k).each{|i|
      position[i+k].must == position[i] + i + 1
      x[position[i]].must == i
      x[position[k+i]].must == i
      x.count(i).must == 2 # implicit constraint which makes is slightly faster
    }

    

    # since we are 0-based we fix index 0 
    x[0].must == 0
    position[0].must == 0

    # symmetry breaking
    x[1].must < x[2*k]

    # Note: the branch on position is placed first, since it's much faster
    #       that if it's placed second
    branch_on position, :variable => :smallest_size, :value => :min 
    branch_on x       , :variable => :smallest_size, :value => :min


  end # end initialize


end # end class

k     = (ARGV[0] || 4).to_i
n_sol = (ARGV[1] || 0).to_i

langford = Langford.new(k)
num_solutions = 0
langford.each_solution{|s| 
  num_solutions += 1
  puts "\nSolution ##{num_solutions}\n";
  # position = s.position.values
  # puts "position: #{position[1..position.length].join(' ')}"
  x = s.x.values
  puts "sol     : #{x[1..x.length].join(' ')}"

  s.search_stats.each{|w,v| puts "#{w}: #{v}"}
  break if n_sol > 0 and num_solutions >= n_sol

}

puts "\nNumber of solutions: #{num_solutions}"