¿Qué tan difícil es una variante del rompecabezas de Sudoku?

8

Sudoku es un rompecabezas bien conocido que se sabe que es NP completo y es un caso especial de un problema más general conocido como cuadrados latinos. Una solución correcta del cuadrado consiste en llenar cada fila y cada columna con números del al con la condición de que cada número aparezca exactamente una vez en cualquier fila o columna.N×N1N

Defino un nuevo problema. La entrada es una solución correcta de Sudoku puzzle (más generalmente problema de cuadrado latino). Me gustaría decidir si hay permutación de filas y permutación de columnas de modo que ninguna fila y ninguna columna contengan triples consecutivos.N×N

Un ejemplo para una fila sin triple consecutivo es 9 5 6 2 3 8 4 7 1. Un ejemplo para una fila con triple consecutivo es 8 9 5 2 3 4 7 6 1. El triple es 2 3 4.

Sospecho que el problema es NP-hard pero no pude encontrar una reducción.

¿Qué tan difícil es resolver esta variante del rompecabezas de Sudoku? ¿Es NP-completo?

EDITAR : Para aclarar, se debe aplicar la misma permutación a las columnas y las filas.

Mohammad Al-Turkistany
fuente
1
Solo una información: para los cuadrados latinos, ¿tiene un ejemplo fácil donde tal permutación no existe?
Vor
¿Por qué la entrada es una cuadrícula correcta? Las permutaciones cambiarán esta propiedad.
saadtaame
@saadtaame Tenga en cuenta que la entrada es una solución correcta del problema del cuadrado latino y no el problema que definí anteriormente.
Mohammad Al-Turkistany
Sí, ¿por qué tiene que ser una solución correcta del cuadrado latino?
saadtaame
@saadtaame de punto fijo porque todas las filas y las columnas de la entrada cuadrado son sólo permutaciones libres de los números de a . 1N
Mohammad Al-Turkistany

Respuestas:

4

Cuando las permutaciones de fila y columna son diferentes y los triples consecutivos tienen que aumentar: la respuesta siempre es SÍ.

Supongamos que la matriz tiene un tamaño de . Considere una permutación aleatoria de las columnas. Cada fila (por sí misma) es una permutación aleatoria. La probabilidad de que los números aparezcan en las posiciones es . Hay opciones para e , y filas diferentes. Por lo tanto, el número esperado de triples consecutivos esN×Ni,i+1,i+2t,t+1,t+21/(N(N1)(N2))N2tiNN(N2)2/(N(N1)(N2))<1. Llegamos a la conclusión de que hay una cierta permutación de las columnas, bajo la cual no hay triples consecutivos en ninguna de las filas. Ahora repita el mismo argumento para las columnas: tenga en cuenta que permutar las filas no puede crear un triple consecutivo en ninguna de ellas.

Cuando las permutaciones de fila y columna son las mismas, y los triples consecutivos pueden aumentar o disminuir: la respuesta sigue siendo SÍ, para suficientemente grande .N

La idea es utilizar la versión asimétrica del lema local de Lovász , a través del artículo de Lu y Székely Usando el lema local de Lovász en el espacio de inyecciones aleatorias . En la prueba anterior, consideramos los eventos para , que para una línea (ya sea una fila o una columna), indican que para . Estos son ejemplos de los eventos canónicos considerados por Lu y Székely: si la permutación aleatoria (permutar tanto filas como columnas) es , entonces tienen la forma , dondeX,i,t,σσ{±1}(i+σδ)=t+δδ{0,1,2}ππ(t)=j0,π(t+1)=j1,π(t+2)=j2jδ=1(i+σδ) . Dos eventos entran en conflicto si o ( esto es en realidad solo una condición necesaria). Cada evento entra en conflicto con a lo sumo otros eventos ( líneas , dos orientaciones, dos formas de conflicto, cinco posiciones en conflicto). Si bien los eventos no conflictivos son en general dependientes, utilizando la versión asimétrica del lema local de Lovász podemos ignorar esto y dejar que nuestro gráfico de dependencia incluya bordes solo para eventos conflictivos. Dado que la probabilidad de que ocurra cada evento esX,i,t,σ,X,i,t,σ {t,t+1,t+2}{t,t+1,t+2}{j0,j1,j2}{j0,j1,j2}2N2251=40N12Np=1/(N(N1)(N2)) y el tamaño de cada vecindario es , el lema se aplica siempre que , es decir Esta condición se cumple para . Concluimos que para , la permutación requerida siempre existe. Usando la versión constructiva reciente de LLL, incluso podemos encontrarlo de manera eficiente.d40N1ep(d+1)1

40eNN(N1)(N2).
N12N12
Yuval Filmus
fuente
Gracias por tu respuesta. ¿Aplicaste la misma permutación en las filas y columnas?
Mohammad Al-Turkistany
No, primero aplico una buena permutación en las columnas y luego una buena permutación en las filas. No hay razón para que sean lo mismo.
Yuval Filmus
Perdón por no ser claro en mi pregunta. Quiero una sola permutación que se aplique a las filas y las columnas simultáneamente.
Mohammad Al-Turkistany
2
Esto es lo que escribió: "decida si hay permutación de filas y permutación de columnas de modo que ...".
Yuval Filmus
Lo siento de nuevo por no ser claro en mi pregunta. Si no le importa, editaré la pregunta para que quede clara.
Mohammad Al-Turkistany