Connecting cells by line and column permutations in a finite grid
Let's try a similar counting argument to the one in the earlier version of my answer, more carefully.

Given an input 0-1 matrix with q nonzeros, define a "solution" to be a permutation of the rows, a permutation of the columns, and the connected 0-1 matrix that one gets as output after performing the permutations. The important observation here is that there are at most $n^2 2^{5q}$ different output matrices possible: once we make one of $n^2$ choices for the position of one of the nonzeros, we can encode the rest of the output matrix in $5q$ bits by doing a preorder traversal of a spanning tree of the nonzeros and recording for each edge in the tree whether it goes to a leaf, whether it is the last edge from its parent, and what its direction is. So the number of solutions is in total at most $n^2 2^{5q} (n!)^2$.

Now each solution works only for a single input, because we can reverse the permutations to get the input back from the output matrix. The number of inputs that have exactly $c$ nonzeros per row is $\binom{n}{c}^n$, and for $c$ constant this can be rewritten $\exp(cn\log n-O(n))$. But for $q=cn$ the number of solutions is $\exp(2n\log n+O(cn))$. For $c&gt;2$, the inputs outnumber the solutions, so there is an unsolvable input.