langford.c
3.77 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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/*
* langford.c
*
* Created on: 24/03/2017
* Author: pedro
*
* http://www.csplib.org/Problems/prob024/
* https://github.com/MiniZinc/minizinc-benchmarks/tree/master/langford
* https://www.cril.univ-artois.fr/~lecoutre/benchmarks.html#
*
* Langford's number problem:
* Arrange 2 sets of positive integers 1..k to a sequence, such that, following the first occurrence 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
*/
#define LANGFORD 0
#include "langford.h"
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include "../config.h"
#include "../constraints/fake_all_different.h"
#include "../constraints/element.h"
#include "../constraints/lt.h"
#include "../constraints/minus_eq.h"
#include "../split.h"
#include "../variables.h"
#if LANGFORD == 0
/*
* Solve the Langford number problem with N values
*/
void run_langford(int* csp_dims) {
int n = csp_dims[0];
unsigned long result;
unsigned int* position = malloc((unsigned int)n * 2 * sizeof(unsigned int));
unsigned int* solution = malloc((unsigned int)n * 2 * sizeof(unsigned int));
int i;
for (i = 0; i < n * 2; i++) {
position[i] = v_new_range(1, 2 * (unsigned int)n, true);
}
for (i = 0; i < n * 2; i++) {
solution[i] = v_new_range(0, (unsigned int)n - 1, false);
}
for (i = 0; i < n; i++) {
c_minus_eq(position[i + n], position[i], i + 2);
c_element(solution, 2 * (unsigned int)n, position[i], (unsigned int)i);
c_element(solution, 2 * (unsigned int)n, position[(unsigned int)n + (unsigned int)i], (unsigned int)i);
}
c_fake_all_different(position, (unsigned int)n * 2);
c_lt(solution[0], solution[2 * (unsigned int)n - 1]);
if (FINDING_ONE_SOLUTION) {
printf("\nFinding one solution for Langford's number with %u numbers on:\n", n);
} else {
printf("\nCounting all the solutions for Langford's number with %u numbers on:\n", n);
}
// Solve the CSP
result = solve_CSP();
if (FINDING_ONE_SOLUTION && result == 1) {
printf("Solution:\n");
vs_print_single_val(solution, (unsigned int)n * 2, 0);
printf("\n");
} else {
printf("%lu solution(s) found\n", result);
}
free(position);
free(solution);
}
#elif LANGFORD == 1
/*
* Solve the Langford number problem with K sets and N values
*/
void run_langford(int* csp_dims) {
int k = csp_dims[0];
int n = csp_dims[1];
unsigned long result;
unsigned int* numbers = malloc(k * n * sizeof(unsigned int));
unsigned int* ordered = malloc(k * n * sizeof(unsigned int));
unsigned int i, j;
for (i = 0; i < k * n; i++) {
numbers[i] = v_new_range(0, k * n - 1, true);
}
c_fake_all_different(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++) {
c_minus_eq(numbers[i * k + j + 1], numbers[i * k + j], i + 2);
}
}
// don't generate symmetrical solutions
unsigned int first = v_new_range(1, k * n, true);
unsigned int last = v_new_range(1, k * n, true);
c_element(numbers, k * n, first, 0);
c_element(numbers, k * n, last, k * n - 1);
c_lt(first, last);
if (FINDING_ONE_SOLUTION) {
printf("\nFinding one solution for Langford's number with N=%u and K=%u.\n", n, k);
} else {
printf("\nCounting all the solutions for Langford's number with N=%u and K=%u.\n", n, k);
}
// Solve the CSP
result = solve_CSP();
if (FINDING_ONE_SOLUTION && result == 1) {
printf("Solution:\n");
vs_print_single_val(numbers, k * n, 0);
for (i = 0; i < k * n; i++) {
ordered[v_get_value(i)] = i / k + 1;
}
for (i = 0; i < k * n; i++) {
printf("%d, ", ordered[i]);
}
printf("\n");
} else {
printf("%lu solution(s) found\n", result);
}
free(numbers);
free(ordered);
}
#endif