#include <stdio.h>
#include <string.h>

#include "fdc_int.h"

// Langford's number problem (CSPLib 024)

/*
  Problem:

  - sorting K sets {1, ..., N} such that:
    - between each consecutive pair of 1's there is one other number
    - between each consecutive pair of 2's there are two other numbers
    - ...
    - between each consecutive pair of N's there are N other numbers

  Modelling:

  - K * N variables representing the positions of the numbers
  - the first K variables represent the position of the 1's
  - the next K variables represent the position of the 2's
  - ...
  - the last K variables represent the position of the N's

  Solution:

  - the variables contain a permutation of 1..N * K (the positions)
  - each pair of adjacent variables from the first K differ by 1 + 1
  - each pair of adjacent variables from the second K differ by 2 + 1
  - ...
  - each pair of adjacent variables from the last K differ by N + 1
*/

#define MAX_K 10	// sets
#define MAX_N 100	// 1..N

static int K = 3;	// default sets
static int N = 9;	// default elements

int main(int argc, char *argv[])
{
  int arg;
  fd_int numbers[MAX_K * MAX_N];
  int ordered[MAX_K * MAX_N];
  int solutions = 0, one_solution = 1;
  int use_label = 0;
  int i, j;
  int seed;

  fd_init(&argc, &argv);

  for (arg = 1; arg < argc; ++arg)
    if (!strcmp(argv[arg], "--all"))
      one_solution = 0;
    else if (!strcmp(argv[arg], "--label"))
      use_label = 1;
    else if (isdigit(*argv[arg]))
      break;
    else
      {
        _fd_error("%s: invalid argument `%s'\n", argv[0], argv[arg]);

        return 2;
      }

  if (argc > arg)
    {
      K = atoi(argv[arg++]);
      N = atoi(argv[arg++]);
    }

#ifdef LOCAL_SEARCH
  seed = time(0);
  //seed = 1206468701;
  //seed = 1208196137; // converges to a local minimum with MCH
  srandom(seed);
  _fd_debug("seed = %u\n", seed);
#endif

  for (i = 0; arg < argc; ++arg, ++i)
    {
      int lb, ub;
      char *s;

      lb = ub = atoi(argv[arg]);
      if (s = strchr(argv[arg], '-'))
	ub = atoi(s + 1);
      numbers[i] = fd_new(lb, ub);
    }

  for (; i < K * N; ++i)
    numbers[i] = fd_new(0, K * N - 1);

  fd_all_different(numbers, K * N);

  if (use_label)
    fd_label(numbers, K * N);

  // don't generate solutions which correspond to exchanging the
  // positions of a number (and are, therefore, identical)
  for (i = 0; i < N; ++i)
    for (j = 0; j < K - 1; ++j)
      fd_minus_eq(numbers[i * K + j + 1], numbers[i * K + j], i + 2);
      // printf("%d %d %d\n", i * K + j + 1, i * K + j, i + 2);

  // don't generate symmetrical solutions
  {
    fd_int first, last;

    first = fd_new(0, K * N - 1);
    last = fd_new(0, K * N - 1);

    fd_element(numbers, K * N, first, 0);
    fd_element(numbers, K * N, last, K * N - 1);

    fd_lt(first, last);
  }

#ifndef COUNT_SOLUTIONS
  while (fd_solve() == FD_OK)
    {
      printf("solution %d:\n", ++solutions);

      for (i = 0; i < K * N; ++i)
	{
	  fd_print(numbers[i]);
	  putchar(' ');
	}
      putchar('\n');

      for (i = 0; i < K * N; ++i)
	{
	  fd_var_single(numbers[i], &j);
	  ordered[j] = i / K + 1;
	}

      for (i = 0; i < K * N; ++i)
	printf("%d ", ordered[i]);
      putchar('\n');

#if !(defined(LOCAL_SEARCH) || defined(DISTRIBUTED_SOLVER))
      if (one_solution)
#endif
	break;
    }

  if (solutions)
    printf("%d solutions found\n", solutions);
  else
    printf("inconsistent CSP\n");

  fd_end();

  return !solutions;
#else /* COUNT_SOLUTIONS */
  fd_solve();

  fd_end();

  return 0;
#endif /* COUNT_SOLUTIONS */
}