Split the matrix 8-ways PUZZLE I have a problem that has been bugging me for the last month, there is a matrix with 8x8 squares, so 64 squares, and with 8 balls placed randomly each in a square. I need to find the solution of how the matrix should be split into 8 parts such that each ball is in a different part and each part has exactly 8 squares.
By the way, each "puzzle" can have multiple, one, or no solutions.
Before:

After:

 A: I don't think there's an easy solution.  In principle you could do this, but in practice I doubt that it is realistic:  For each ball $b$, let $S_b$ be the set of all connected sets of cardinality $8$ containing $b$ and no other ball.  Take binary variables $x_i$ for all members $i$ of all $S_b$.  Then you want to satisfy the conditions
$$\eqalign{\sum_{i \in S_b} x_i &= 1\ \text{for each $b$}\cr
           x_i + x_j &\le 1 \ \text{if $x_i \in S_b$ and $x_j \in S_{b'}$ with $b \ne b'$ and $i \cap j \ne \emptyset$}\cr} $$
Use a SAT solver or integer linear programming.
In cases where a solution exists, you might find one using heuristic methods such as tabu search or simulated annealing.
A: You can model this as a set partitioning problem as follows.  Let $S$ be the set of all connected sets of cardinality 8 that contain exactly 1 ball.  For the sample puzzle above, it turns out that $|S|=23617$.  Let $N=\{1,\dots,8\}$.  For $(i,j) \in N \times N$, let $S_{i,j} \subset S$ be the subset of sets that contain cell $(i,j)$.  For $s\in S$, let binary decision variable $x_s$ indicate whether set $s$ is selected.  The constraints are:
$$\sum_{s\in S_{i,j}} x_s = 1 \quad \text{for $(i,j)\in N \times N$}$$
There are multiple solutions, including this one:

 

