Me gustaría saber si el siguiente problema ha sido estudiado antes y si cualquier solución que se conoce.
Sea G ser un número finito (MxN) de la cuadrícula, S un subconjunto de G células (las "migajas"). Dos migas se dice que es (localmente) conectado si sus coordenadas diferentes a la mayoría de uno (es decir, si se dibuja como plazas, comparten al menos un punto de esquina).
Ahora, uno puede tratar de conectar las migajas (en su conjunto) por permutating las líneas y las columnas de la cuadrícula. En otras palabras, el objetivo es llegar con una permutación de las líneas y una permutación de las columnas, de manera que cualquiera de los dos migas en el resultado de la cuadrícula están conectados por una cadena de (a nivel local) conectado migas.
Pregunta: hay siempre una solución?
No sé bien cómo atacar. A falta de una mejor idea, he escrito un raw programa que busca soluciones por la fuerza bruta (que genera las permutaciones al azar y se comprueba si el resultado de la cuadrícula tiene sus migas conectado). El programa hasta ahora siempre se encuentran soluciones en pequeño (10x10 o 7x14) las rejillas, y las grandes redes están claramente fuera del alcance de su estrategia simplista (sería demasiado largo para tropezar al azar a través de una solución).
Aquí está un ejemplo de una cuadrícula resuelto por el programa:
Inicial de la cuadrícula (migas se denota por X, las celdas vacías por puntos):
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 .
Solución:
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 . . .
Naturalmente, el problema puede ser fácilmente generalizado a cualquier dimensión d > 2. Supongo que otras generalizaciones podría ser considerado.
Gracias de antemano,
Yann David
PD: he publicado la pregunta en CS de la teoría de intercambio de la pila en http://cstheory.stackexchange.com/questions/9015/connecting-cells-by-line-and-column-permutations-in-a-finite-grid, yo no soy consciente de ninguna manera para conectar a las dos preguntas.
