golfers.c
3.29 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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
/* Social golfers */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "fdc_int.h"
#define MAX_P MAX_VARIABLES
#define MAX_G MAX_VARIABLES
int main(int argc, char *argv[])
{
int P = 12; // no. of players
int G = 4; // no. of groups per week
int K = 3; // players per group
int W = 2; // no. of weeks
int GW; // total groups
fd_int *vs;
#define vs(r, c) vs[(r) * GW + (c)]
fd_int *ts, *us;
int p, g, p0, p1, g0, g1, w;
int solutions = 0, one_solution = 1;
int use_label = 0;
int i;
fd_init(&argc, &argv);
for (i = 1; i < argc; ++i)
if (!strcmp(argv[i], "--all"))
one_solution = 0;
else if (!strcmp(argv[i], "--label"))
use_label = 1;
else if (argc - i < 3)
{
fd__error("must give G, K, and W (or nothing)\n");
return 1;
}
else
{
G = atoi(argv[i++]);
K = atoi(argv[i++]);
W = atoi(argv[i]);
}
P = G * K;
GW = G * W;
vs = calloc(P * GW, sizeof(fd_int));
ts = calloc(P > GW ? P : GW, sizeof(fd_int));
us = calloc(P > GW ? P : GW, sizeof(fd_int));
for (p = 0; p < P; ++p)
for (g = 0; g < GW; ++g)
vs(p, g) = fd_new(0, 1);
if (use_label)
fd_label(vs, P * GW);
// a player appears in W groups
for (p = 0; p < P; ++p)
fd_sum(vs + GW * p, GW, W);
// K players per group
for (g = 0; g < GW; ++g)
{
for (p = 0; p < P; ++p)
ts[p] = vs(p, g);
fd_sum(ts, P, K);
}
// no player should be in another group with another player more
// than once: the scalar (or dot) product between any two rows must
// not exceed 1
for (p0 = 0; p0 < P; ++p0)
for (p1 = p0 + 1; p1 < P; ++p1)
{
for (g = 0; g < GW; ++g)
{
ts[g] = vs(p0, g);
us[g] = vs(p1, g);
}
fd_knapsack2(ts, us, GW, fd_new(0,1));
}
// every G groups correspond to one week and no player can be in
// more than one: the scalar product between any two columns within
// every G groups must be 0
for (w = 0; w < W; ++w)
for (g0 = 0; g0 < G; ++g0)
for (g1 = g0 + 1; g1 < G; ++g1)
{
for (p = 0; p < P; ++p)
{
ts[p] = vs(p, w * G + g0);
us[p] = vs(p, w * G + g1);
}
fd_sum_prod(ts, us, P, 0);
}
// try to eliminate solutions which result from exchanging rows
// and/or columns
// XXX: quite incomplete
#if 0
// constrain the first row to be of the form 1 0...0 1 0...0 ... 1 0...0
{
fd_int zero = fd_new(0, 0);
for (g = 0; g < W; ++g)
fd_gt(vs(0, g * G), zero);
}
#endif
// constrain the first column to be of the form 1 ... 1 0 ... 0
for (p = 1; p < P; ++p)
fd_ge(vs(p - 1, 0), vs(p, 0));
while (fd_solve() == FD_OK)
{
printf("solution %d:\n", ++solutions);
for (p = 0; p < P; ++p)
{
for (g = 0; g < GW; ++g)
{
fd_print(vs(p, g));
putchar(' ');
}
putchar('\n');
}
for (w = 0; w < W; ++w)
{
for (g = 0; g < G; ++g)
{
printf(" (");
for (p = 0, p0 = 0; p0 < K; ++p)
if (fd_var_value(vs(p, w * G + g)) == 1)
printf("%d%c", p, ++p0 == K ? ')' : ' ');
}
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;
}