**The problem**:

I have a system of **N** linear equations, with **K** unknowns; and **K > N**.
Although the equations are over $\mathbb Z$, the unknowns can only take the values **0** or **1**.

Here's an example with **N**=11 equations and **K**=15 unknowns:

$1 = x_1 + x_9$

$2 = x_{1} + x_{2} + x_{10}$

$2 = x_{2} + x_{3} + x_{11}$

$2 = x_{3} + x_{12}$

$2 = x_{9} + x_{4} + x_{13}$

$2 = x_{10} + x_{4} + x_{5} + x_{14}$

$2 = x_{11} + x_{5} + x_{6} + x_{15}$

$2 = x_{12} + x_{6}$

$2 = x_{13} + x_{7}$

$2 = x_{14} + x_{7} + x_{8}$

$1 = x_{15} + x_{8}$

Things that will always hold true in the general case:

- Every coefficient is $1$.
- In the entire collection of equations, each $x_i$ appears exactly twice.
- There are exactly two equations of the form $x_i + x_j = 1$.
- All the other equations will have $2$ as the constant.

**Some observations**:

- If you sum all of the above equations and divide both sides by $2$,
you get $\sum_{i=1}^{i=K}x_i=N-1$. In this case,

$x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} + x_{8} + x_{9} + x_{10} + x_{11} + x_{12} + x_{13} + x_{14} + x_{15} = 10$.

So, in any solution, there will be exactly**N-1**1's and**K-(N-1)**0's.

**My Questions**:

- How many solutions does this general system have?
- Is there a
**fast**way to find these solutions?

*FWIW, I encountered this problem when trying to find the longest (hamiltonian) path between two points in a square lattice.*

numberof solutions? – Aditya Bhatt Nov 2 '11 at 13:36