**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.*



How many 0, 1 solutions would this system of underdetermined linear equations have?
In complexity terms, no "efficient" (polynomial time) solution is likely.


However in practical terms you may be able to solve quite large problems of this nature, either by using integer linear programming software (I recommend Gurobi) or constraint satisfaction programming software.


For example, here is how you would do it in the CSP solver "Minion"


Create a file called something like "problem.min" containing the following (notice that I have changed x15 to x[0] to use an array of variables).



```
MINION 3
**VARIABLES**
BOOL x[15]
**CONSTRAINTS**
sumgeq([x[1],x[9]],1)
sumleq([x[1],x[9]],1)

sumgeq([x[1],x[2],x[10]],2)
sumleq([x[1],x[2],x[10]],2)

sumgeq([x[2],x[3],x[11]],2)
sumleq([x[2],x[3],x[11]],2)

sumleq([x[3],x[12]],2)
sumgeq([x[3],x[12]],2)

sumleq([x[9],x[4],x[13]],2)
sumgeq([x[9],x[4],x[13]],2)

sumgeq([x[10],x[4],x[5],x[14]],2)
sumleq([x[10],x[4],x[5],x[14]],2)

sumleq([x[11],x[5],x[6],x[0]],2)
sumgeq([x[11],x[5],x[6],x[0]],2)

sumleq([x[6],x[12]],2)
sumgeq([x[6],x[12]],2)

sumleq([x[7],x[13]],2)
sumgeq([x[7],x[13]],2)

sumleq([x[7],x[8],x[14]],2)
sumgeq([x[7],x[8],x[14]],2)

sumgeq([x[8],x[0]],1)
sumleq([x[8],x[0]],1)

**EOF**

```

(Notice that minion makes the somewhat idiosyncratic decision to require equalities to be expressed as two opposite inequalities, but apart from that the syntax is obvious.)


Then just run



```
$ minion -findallsols problem.min

```

In less than 0.05 seconds it reports 5 solutions.


