not appear in S, this reduces the number of variables by
1.
Reducing the number of variables reduces the running
time of our algorithm as well, which is exponential in the
number of variables. It turns out that we are guaranteed
that there exist at least n such pairs of S’s and Y ’s. This
enables us to reduce the number of variables from M
to M − n, which in turn reduces our running time to
O(nm2
M
−n
).
There are n such S and Y pairs because the encod-
ing of a CSP will have a single equation for each CSP
variable, representing the fact that the variable must be
assigned exactly one value.
3
Let Y correspond to the
equation which constrains the CSP variable v to have
exactly one value, and consider the binomials in Φ that
contain Y . These are exactly the binomials that cor-
respond to possible values for v, so there can be only
m of them. Furthermore, this set of binomials forms
an appropriate S, since no Y
0
corresponding to another
CSP variable can appear. There are n such Y ’s, one per
CSP variable, and these Y ’s will always app ear in the
coefficient(s) that we need to calculate.
It is even possible to take advantage of such S’s and
Y ’s when Y does not necessarily appear in the required
coefficients. (Recall that this is a result of the integer
linear programming equation that corresponds to Y ac-
tually representing an inequality, as discussed at the end
of section 3.2.) If this happens, we can replace S by
S
0
+ S
1
and still discard Y . This has the effect of sum-
ming the coefficients that stand for the solutions to the
two implicit systems of equalities early in the computa-
tion, rather than waiting to multiply Φ out before cal-
culating this sum.
We can thus reduce the number of variables by at least
n. As we saw in section 4, each binomial corresponds
to a p ossible assignment v
i
←d
j
. The ordering that is
guaranteed to reduce the number of variables by n cor-
responds to considering all the assignments for a fixed
v
i
before moving on to the next CSP variable. On the
n-queens problem this is equivalent to multiplying out
the binomials in row-major order.
7 Some new bounds
An additional advantage of our approach is that we can
produce non-trivial upper bounds for solving certain con-
straint satisfaction problems. So far, we have confined
out attention to CSP’s based on placing pieces on a
chessboard.
The classic such problem is the n-queens problem,
which was known to Gauss. The n-queens problem con-
sists of placing n queens on an n-by-n chessboard so that
no two queens attack. A variation of this problem is the
toroidal n-queens problem, where lines of attack between
3
An encoding that does not have this property corre-
sponds to a CSP whose unsatisfiability can be easily detected
via arc consistency
[
Mackworth, 1977
]
.
queens are considered to ‘wrap’ as if the board were a
torus. The toroidal n-queens problem has strictly fewer
solutions than the (regular) n-queens problem.
To our knowledge there is no known bound for CSP
search algorithms for this problem, beyond the trivial
bound of n
n
. In fact, there is some evidence that the
number of solutions to the toroidal problem (and hence
to the regular problem) is larger than exponential
[
Rivin
and Vardi, 1989
]
.
The toroidal n-queens problem can be formulated as a
simple set of equations. There are n
2
variables x
j
. There
are also 4n equations, one for each column, row, diagonal
(top to bottom) and anti-diagonal. So we have M =4n,
N = n
2
. Applying the above results, our algorithm can
determine the number of solutions in time O(n
2
8
n
).
For the regular n-queens problem, again N = n
2
, but
this time there are 2(2n − 1) inequalities for the diago-
nals. This gives us M =6n − 2, and a running time of
O(n
2
32
n
).
However, if we do the multiplication in row-major or-
der, it turns out that only 3n variables will need to be
active at once. This can be seen by noting that the top
row involves 3n constraints. Moving to the next row
adds a new row constraint and removes the old row con-
straint. The far left square of the new row eliminates
an antidiagonal constraint (all the squares involved in
that constraint have been eliminated), and adds a new
diagonal constraint, while the far right square eliminates
a diagonal constraint and adds a new antidiagonal con-
straint. This gives us a much better bound of O(n
2
8
n
).
Our preliminary experiments with this algorithm have
been promising.
8 Conclusions
We have shown a surprising connection between solv-
ing search problems and multiplying certain polynomi-
als. The performance is very simple to analyze, and we
can show new bounds for several constraint satisfaction
problems.
Our approach also holds our the possibility of apply-
ing sophisticated algebraic techniques to constraint sat-
isfaction problems. For example, it is possible that the
coefficient of Y in Φ can be estimated, thus providing
an approximate count of the number of solutions. Also,
complex mathematical results like those in
[
Anshel and
Goldfeld, 1988
]
can be used to provide an upper bound
on the number of solutions by studying the generating
function directly, using the theory of modular forms.
Our algorithm also shares some surprising properties
with Seidel’s method
[
Seidel, 1981
]
. Like Seidel, we pro-
duce a method which is easy to analyze, and which gives
a bound that is exponential in a certain parameter of
the problem. Seidel’s parameter f is a property of the
topology of the constraint graph, which can be shown
to be O(
√
n) for planar graphs. Our parameter M is a
property of the way the problem gets encoded as an in-