/*
 * costas.c
 *
 *  Created on: 09/12/2014
 *      Author: pedro
 *
 *      http://www.csplib.org/Problems/prob076/
 *      https://github.com/MiniZinc/minizinc-benchmarks/tree/master/costas-array
 *      https://www.cril.univ-artois.fr/~lecoutre/benchmarks.html#
 *
 *		Costas Array problem:
 *      A Costas array can be regarded geometrically as a set of n points lying on the squares of a n×n checkerboard,
 *      such that each row or column contains only one point, and that all of the n(n-1)/2 displacement vectors
 *      between each pair of dots are distinct.
 */

#include "costas.h"

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>

#include "../config.h"
#include "../constraints/eq_var.h"
#include "../constraints/fake_all_different.h"
#include "../constraints/linear_var.h"
#include "../constraints/lt.h"
#include "../constraints/ne.h"
#include "../constraints/var_eq_minus.h"
#include "../constraints/var_eq_plus.h"
#include "../split.h"
#include "../variables.h"

#define diffs(a, b) differences[(a) * n + (b)]

/*
 * Solve the Costas Array problem with N values
 */
void run_costas(int* csp_dims) {
	int n = csp_dims[0];
	unsigned long result;
	unsigned int *costas, *differences;
	int coeffs[] = { 1, 1, -1 };
	unsigned int diffeq[3];
	int i, j;

	costas = malloc((unsigned int)n * sizeof(unsigned int));

	for (i = 0; i < n; i++) {
		costas[i] = v_new_range(0, (unsigned int)n-1, true);
	}

	c_fake_all_different(costas, (unsigned int)n);

	differences = malloc((unsigned int)n * (unsigned int)n * sizeof(unsigned int));

	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (i < j) {
				diffs(i, j)= v_new_range(0, 2 * ((unsigned int)n - 1), false);
			}
		}
	}

	// How do the positions in the Costas array relate to the elements of the distance triangle.
	diffeq[0] = v_new_val((unsigned int)n - 1);
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (i < j) {
				diffeq[1] = costas[j];
				diffeq[2] = costas[j - 1 - i];

				c_linear_var(coeffs, diffeq, 3, diffs(i, j));
			}
		}
	}

	// All entries in a particular row of the difference triangle must be distint.
	j = 1;
	for (i = 0; i < n; i++) {
		c_fake_all_different(&diffs(i, j), (unsigned int)n - (unsigned int)j);
		j++;
	}

	// All the following are redundant - only here to speed up search.

	// Symmetry Breaking
	if (1 < n) {
		c_lt(costas[0], costas[n - 1]);
	}

	// We can never place a 'token' in the same row as any other.
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (i < j) {
				c_ne(diffs(i, j), diffeq[0]);
			}
		}
	}

	for (i = 2; i < n; i++) {
		for (j = 2; j < n; j++) {
			if (i < j) {
				diffeq[0] = diffs(i - 2, j - 1);
				diffeq[1] = diffs(i, j);
				diffeq[2] = diffs(i - 1, j - 1);
				c_linear_var(coeffs, diffeq, 3, diffs(i - 1, j));
			}
		}
	}

	if (FINDING_ONE_SOLUTION) {
		printf("\nFinding one solution for Costas Array with %u dots.\n", n);
	} else {
		printf("\nCounting all the solutions for Costas Array with %u dots.\n", n);
	}

	// Solve the CSP
	result = solve_CSP();

	if (FINDING_ONE_SOLUTION && result == 1) {
		printf("Solution:\n");
		vs_print_single_val(costas, (unsigned int)n, 1);
		printf("\n");
	} else {
		printf("%lu solution(s) found\n", result);
	}

	free(costas);
	free(differences);
}