# {0,1}-solutions for integer equations via lattice base reduction?

I would like to find $\{0,1\}$-solutions of a system of equations of the form $$\left\{\begin{array}{c}\sum_{i\in I_1}x_i=1\\\sum_{i\in I_2}x_i=1\\\vdots\\\sum_{i\in I_k}x_i=1\end{array}\right.$$

where $x_1,\ldots,x_n\in\{0,1\}$ are the variables and $I_1,I_2,\ldots,I_k$ are given subsets of $\{1,2,\ldots,n\}$.

I have now been solving this system by reducing its matrix over $\mathbb{Q}$ and then iterating over all possible combinations for the free variables in $\{0,1\}$, and verifying if the other variables are also in $\{0,1\}$ then. However that is likely not the best way. So my questions:

1. Several people have mentioned that "Lattice base reduction" provides a good solution to this. Unfortunately, when looking that up, I fail to see how that would make this system of equations easier to solve. What is the link?
2. Are there any other methods that I should be aware of for solving this kind of problems? Bonus points if not all constant coefficients have to be $1$, then I could add a few more equations to reduce my search space.

Sudoku puzzles can be reduced to the system of equations that has the same structure as yours. In Sudoku puzzles, there should be one and only one 1 in each row, column and box; there should be one and only one 2 in each row, column and box etc. You can write these conditions as a system above. Let $x_{n, r, c}$ be 1 if the number $n$ is in row $r$, column $c$, and $0$ otherwise; $n, r, c$ $\in$ $\{1, 2, \dots, 9\}$. You will have 3 types of subsets.
The row equations are: $\forall r, n \in \{1, 2, \dots, 9\}$ will correspond to subsets $$I_{r, n} = \bigcup_{\forall c \in \{1, \dots, 9\}} \{n, r, c\}$$ Column equations are: $\forall c, n \in \{1, 2, \dots, 9\}$ will correspond to subsets $$I_{c, n} = \bigcup_{\forall r \in \{1, \dots, 9\}} \{n, r, c\}$$ Finally, box equations are: $\forall R, C \in \{0, 3, 6\}, n \in \{1, 2, \dots, 9\}$ will correspond to subsets $$I_{R, C, n} = \bigcup_{\forall r, c \in \{1, 2, 3\}} \{n, R + r, C + c\}$$
All sudoku algorighm I have seen can be used for general problem - the one you state above. See http://en.wikipedia.org/wiki/Sudoku_solving_algorithms and http://www.math.cornell.edu/~mec/Summer2009/meerkamp/Site/Solving_any_Sudoku_II.html among others. Just replace "rows, columns and boxes" by "sets $I_\cdot$", and you can apply them right away. And, I believe, right hand equation values can be different from 1, still, the same algorithms will apply.