I'd like to know whether the following simple problem has been studied before and if any solution is known.
Let G be a finite (MxN) grid, S a subset of G's cells (the "crumbs"). Two crumbs are said to be (locally) connected if their coordinates differ by at most one (i.e., if drawn as squares, they share at least one corner point).
Now, one can try to connect the crumbs (their set as a whole) by permutating the lines and the columns of the grid. In other words, the goal is to come up with a permutation of the lines and a permutation of the columns so that any two crumbs in the resulting grid are connected by a chain of (locally) connected crumbs.
Question: is there always a solution?
I don't quite know how to attack it. For lack of a better idea, I have written a raw program that looks for solutions by brute force (it generates the permutations at random and checks whether the resulting grid has its crumbs connected). The program has so far always found solutions on smallish (10x10 or 7x14) grids, and larger grids are clearly out of reach of its simplistic strategy (it would take too long to stumble at random across a solution).
Here is an example of a grid solved by the program:
Initial grid (crumbs are denoted by X's, empty cells by dots):
0 1 2 3 4 5 6 7 8 9 0 X . X X . X . X X . 1 X . . . . X . . . . 2 . . X . . . . X . X 3 . X . . X . X . . X 4 . . . X . . . . . . 5 X X . . . X X . X . 6 . . . X . . . . X . 7 X . X . . X . . . . 8 X . . . X . . X X .
6 1 4 7 8 2 9 3 5 0 1 . . . . . . . . X X 4 . . . . . . . X . . 5 X X . . X . . . X X 8 . . X X X . . . . X 7 . . . . . X . . X X 0 . . . X X X . X X X 3 X X X . . . X . . . 6 . . . . X . . X . . 2 . . . X . X X . . .
Naturally, the problem can readily be generalized to any dimension d > 2. I suppose other generalizations could be considered.
Thanks in advance,
NB: I cross-posted the question on CS theory stack exchange at http://cstheory.stackexchange.com/questions/9015/connecting-cells-by-line-and-column-permutations-in-a-finite-grid, I'm not aware of any way to connect the two questions.