Connexion de cellules par permutations de lignes et de colonnes dans une grille finie

Je voudrais savoir si le problème simple suivant a déjà été étudié et si une solution est connue.

Soit G une grille finie (MxN), S un sous-ensemble de cellules de G (les "miettes"). On dit que deux miettes sont connectées (localement) si leurs coordonnées diffèrent d'au plus une (c'est-à-dire que si elles sont dessinées en carrés, elles partagent au moins un point d'angle).

Maintenant, on peut essayer de relier les miettes (leur ensemble dans son ensemble) en permutant les lignes et les colonnes de la grille. En d'autres termes, l'objectif est de proposer une permutation des lignes et une permutation des colonnes de sorte que deux miettes dans la grille résultante soient connectées par une chaîne de miettes connectées (localement).

Question: y a-t-il toujours une solution?

Je ne sais pas trop comment l'attaquer. Faute d'une meilleure idée, j'ai écrit un programme brut qui recherche des solutions par force brute (il génère les permutations au hasard et vérifie si la grille résultante a ses miettes connectées). Jusqu'à présent, le programme a toujours trouvé des solutions sur des grilles de petite taille (10x10 ou 7x14), et les grilles plus grandes sont clairement hors de portée de sa stratégie simpliste (il faudrait trop de temps pour tomber au hasard sur une solution).

Voici un exemple de grille résolue par le programme:

Grille initiale (les miettes sont désignées par des X, les cellules vides par des points):

   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 .

Solution:

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

Naturellement, le problème peut être facilement généralisé à n'importe quelle dimension d> 2. Je suppose que d'autres généralisations pourraient être envisagées.

Merci d'avance,

Yann David

ds.algorithms graph-theory graph-algorithms Yann David
la source

problème intéressant. y a-t-il une application?

Suresh Venkat

@Tsuyoshi: vous avez raison, le chiffre que j'ai publié a une solution (celle que vous avez fournie). Je l'ai effacé.

Marzio De Biasi,

Le crosspost simultané est déconseillé. math.stackexchange.com/questions/83231/…

Tsuyoshi Ito

Essayons un argument de comptage similaire à celui de la version précédente de ma réponse, plus attentivement.

$n^2 2^{5q}$ $n^2$ $5q$ $n^2 2^{5q} (n!)^2$

$c$ $\binom{n}{c}^n$ $c$ $\exp(cn\log n-O(n))$ $q=cn$ $\exp(2n\log n+O(cn))$ $c>2$

David Eppstein
la source

c = 3

$c=3$

o (n)

$o(n)$

n > 6 * 2^{15} / e^{2}

$n > 6*2^{15}/e^2$

C'est une curieuse coïncidence numérique. J'ai posé des questions à ce sujet sur mathoverflow.net/questions/81368/…

David Eppstein

C'est en effet une preuve élégante et convaincante. (J'ai pris un peu de temps pour détailler les approximations pour mon propre bénéfice.) Il reste à voir si quelqu'un parviendra à trouver un contre-exemple concret. Le commentaire de @ hardmath ci-dessus suggère que cela pourrait être difficile (le CE serait une bête laide); maintenant, il n'est pas nécessaire d'avoir le même nombre de miettes dans toutes les rangées d'un CE.

Yann David

Connexion de cellules par permutations de lignes et de colonnes dans une grille finie

Réponses: