costas.c
3.22 KB
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
/*
* 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);
}