exactly-one.c
2.36 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
/* exactly-one */
static int fd_exactly_one_propagate(fd_constraint this, fd_int revise)
{
int value;
int changed = 0, candidates = 0, which = -1;
int i;
// only revise if one other variable has the requested value
for (i = 0; i < this->nvariables; ++i)
if (VAR(this, i) != revise &&
fd_var_single(VAR(this, i), &value) &&
value == this->constants[0])
{
changed |= _fd_var_del_val(value, revise);
candidates++;
break;
}
if (changed && fd_domain_empty(revise))
return FD_NOSOLUTION;
if (changed)
_fd_revise_connected(this, revise); // XXX: NULL or this?
#if 01
// if any (other) variable is set to the required value, stop
// (if more than one variable is set to the value, it will be
// detected in another propagation step, which is (hopefully)
// already scheduled)
if (candidates)
return FD_OK;
// XXX: if value only belongs to one variable (revise?) domain, the
// variable could be set to it
candidates = 0;
for (i = 0; i < this->nvariables; ++i)
if (_fd_var_contains_val(VAR(this, i), this->constants[0]))
{
if (++candidates > 1)
// more than one variable has the value in its domain
break;
which = i;
}
// if there is no variable whose domain contains the requested value,
// no solution can be reached
if (candidates == 0)
return FD_NOSOLUTION;
// if the value only belongs to one variable's domain, that variable
// can be set to it
if (candidates == 1 && !fd_var_single(VAR(this, which), NULL))
if (VAR(this, which) == revise)
{
_fd_var_set_value(revise, this->constants[0]);
if (!changed)
_fd_revise_connected(NULL, revise);
}
else
{
_fd_var_set_value(VAR(this, which), this->constants[0]);
_fd_revise_connected(NULL, VAR(this, which));
}
#endif
return FD_OK;
}
fd_constraint fd_exactly_one(fd_int *variables, int nvariables, int value)
{
fd_constraint c = _fd_constraint_new(nvariables, 1);
int i;
if (c)
{
for (i = 0; i < nvariables; ++i)
c->variables[i] = FD_INT2C_VAR(variables[i]);
c->constants[0] = value;
#ifdef CONSTRAINT_CLASS
c->kind = FD_CONSTR_EXACTLY_ONE;
#else /* CONSTRAINT_CLASS */
c->propagator = fd_exactly_one_propagate;
#endif /* CONSTRAINT_CLASS */
for (i = 0; i < nvariables; ++i)
_fd_var_add_constraint(VAR(c, i), c);
_fd_add_constraint(c);
}
return c;
}