2
$\begingroup$

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.
$\endgroup$
1
$\begingroup$

Your question is very similar to Sudoku type of problems.

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.

Hope this helps!

$\endgroup$
  • $\begingroup$ Thanks! That second link seems to give an error though: Forbidden You don't have permission to access /~mec/Summer2009/meerkamp/Site/Solving_any_Sudoku_II.html on this server. $\endgroup$ – user1111929 Sep 30 '14 at 18:35
  • 1
    $\begingroup$ It was working a few minutes ago, and Solutions part I still works (math.cornell.edu/~mec/Summer2009/meerkamp/Site/…) Hopefully this link will resuscitate soon. Usual googling "sudoku algorithms" will yield many more options, if you need them. $\endgroup$ – Yulia V Sep 30 '14 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.