all-different.c
3.54 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
164
165
166
167
168
169
170
171
/* all-different */
#ifdef USE_MATCHING
#include "matching.h"
static int fd_all_different_filter(fd_constraint this)
{
#ifdef CONSTRAINT_TEMPS
int **memory;
int ok;
assert(!fd__constraint_data_valid(this));
// memory is allocated in _fd_find_matching()
memory = (int **) &constraint_memory[this->index];
ok = _fd_find_matching(this, memory);
if (ok)
fd__constraint_remember(this);
return ok ? FD_OK : FD_NOSOLUTION;
#else
return _fd_find_matching(this) ? FD_OK : FD_NOSOLUTION;
#endif /* CONSTRAINT_TEMPS */
}
static int fd_all_different_propagate2(fd_constraint this, fd_int culprit)
{
#ifdef CONSTRAINT_TEMPS
int *memory;
if (!fd__constraint_data_valid(this))
return fd_all_different_filter(this);
// memory is allocated in _fd_find_matching()
memory = constraint_memory[this->index];
return _fd_update_matching(this, culprit, memory) ? FD_OK : FD_NOSOLUTION;
#else
return fd_all_different_filter(this);
#endif /* CONSTRAINT_TEMPS */
}
#else /* USE_MATCHING */
static int fd_all_different_filter(fd_constraint this)
{
int value;
int i, j;
// only filter wrt variables whose domain is a singleton
for (i = 0; i < this->nvariables; ++i)
if (fd_var_single(VAR(this, i), &value))
for (j = 0; j < this->nvariables; ++j)
if (j != i)
{
fd_int revise = VAR(this, j);
if (_fd_var_del_val(value, revise))
{
if (fd_domain_empty(revise))
return FD_NOSOLUTION;
if (i < j)
_fd_revise_connected(this, revise);
else
_fd_revise_connected(NULL, revise);
}
}
return FD_OK;
}
static int fd_all_different_propagate2(fd_constraint this, fd_int culprit)
{
int value;
int i;
// only revise if culprit's domain is a singleton
if (!fd_var_single(culprit, &value))
return FD_OK;
for (i = 0; i < this->nvariables; ++i)
if (VAR(this, i) != culprit)
{
fd_int revise = VAR(this, i);
if (_fd_var_del_val(value, revise))
{
if (fd_domain_empty(revise))
return FD_NOSOLUTION;
_fd_revise_connected(NULL, revise);
}
}
return FD_OK;
}
#endif /* USE_MATCHING */
static int fd_all_different_propagate(fd_constraint this, fd_int revise)
{
int value;
int changed = 0;
#ifdef USE_ENTAILED
int set = 0;
#endif
int i;
// only revise wrt variables whose domain is a singleton
for (i = 0; i < this->nvariables; ++i)
if (VAR(this, i) != revise &&
fd_var_single(VAR(this, i), &value))
{
changed |= _fd_var_del_val(value, revise);
#if defined(USE_ENTAILED) && 0
set++;
#endif
}
if (changed && fd_domain_empty(revise))
return FD_NOSOLUTION;
#if defined(USE_ENTAILED) && 0
// XXX: hampers performance when not optimised
if (set == this->nvariables - 1)
_fd_constraint_set_entailed(this);
#endif
if (changed)
if (fd_var_single(revise, NULL))
_fd_revise_connected(NULL, revise); // XXX?
else
_fd_revise_connected(this, revise);
return FD_OK;
}
fd_constraint fd_all_different(fd_int *variables, int nvariables)
{
fd_constraint c;
int i;
if (nvariables == 2)
return fd_ne(variables[0], variables[1]);
c = _fd_constraint_new(nvariables, 0);
if (c)
{
for (i = 0; i < nvariables; ++i)
c->variables[i] = FD_INT2C_VAR(variables[i]);
#ifdef CONSTRAINT_CLASS
c->kind = FD_CONSTR_ALL_DIFFERENT;
#else /* CONSTRAINT_CLASS */
c->propagator2 = fd_all_different_propagate2;
c->propagator = fd_all_different_propagate;
#endif /* CONSTRAINT_CLASS */
for (i = 0; i < nvariables; ++i)
_fd_var_add_constraint(VAR(c, i), c);
_fd_add_constraint(c);
}
return c;
}