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:
On
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:
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.