Sudoku con propiedades especiales

Question

Sudoku es un rompecabezas cuyo objetivo es llenar una cuadrícula de 9×9 con dígitos, de modo que cada columna, cada fila y cada una de las nueve subcuadrículas de 3×3 que componen la cuadrícula (también "bloques de sudoku") contengan todos los dígitos del 1 al 9.

Definamos bloque como una subcuadrícula de 3x3 (que no forma necesariamente uno de los bloques del sudoku, sino que los incluye) que contiene todos los dígitos del 1 al 9.

Definamos N como un número de todos los bloques válidos en la cuadrícula.

Para el sudoku habitual $N=9$ .

El máximo teóricamente posible $N=49$ (7 bloques por fila*7 bloques por columna).

He encontrado un sudoku con $N=10$ para demostrar que los rompecabezas con $N>9$ existe. Aquí hay una:

+-------+-------+-------+
| 3 9 6 | 4 1 5 | 2 7 8 |
| 1 2 5 | 7 3 8 | 4 6 9 |
| 4 7 8 | 2 6 9 | 3 1 5 |
+-------+-------+-------+
| 7 5 9 | 6 4 2 | 8 3 1 |
| 8 4 3 | 5 9 1 | 7 2 6 |
| 2 6 1 | 3 8 7 | 5 9 4 |
+-------+-------+-------+
| 5 3 4 | 9 2 6 | 1 8 7 |
| 6 8 7 | 1 5 3 | 9 4 2 |
| 9 1 2 | 8 7 4 | 6 5 3 |
+-------+-------+-------+

El décimo bloque está en la esquina superior derecha:

5 2 7
8 4 6
9 3 1

Y aquí hay otra con $N=33$ ( $N = 3*7 + 3*7 - 9$ )

+-------+-------+-------+
| 1 2 3 | 4 5 6 | 7 8 9 |
| 4 5 6 | 7 8 9 | 1 2 3 |
| 7 8 9 | 1 2 3 | 4 5 6 |
+-------+-------+-------+
| 2 3 1 | 5 6 4 | 8 9 7 |
| 5 6 4 | 8 9 7 | 2 3 1 |
| 8 9 7 | 2 3 1 | 5 6 4 |
+-------+-------+-------+
| 3 1 2 | 6 4 5 | 9 7 8 |
| 6 4 5 | 9 7 8 | 3 1 2 |
| 9 7 8 | 3 1 2 | 6 4 5 |
+-------+-------+-------+

Preguntas:

1. ¿Existe un sudoku con N=49? No
2. En caso afirmativo, ¿de qué se trata?
3. Si no, ¿cuál es el máximo N posible? ¿Por qué?

Actualización . Esta actualización está totalmente basada en la respuesta y prueba de @Emisor.

Supongamos que $N=49$ posible, intentemos generar un rompecabezas:

+-------+--- 
| 1 2 3 | X 
| 4 5 6 | Y 
| 7 8 9 | Z
+-------+---
| A B C | D

El bloque de la primera cifra debe tomarse como nuestro "punto de partida". Como no hay otros números en el tablero, tenerlos ordenados no supone ninguna diferencia, por ahora.

Ahora, para $N=49$ deben cumplirse varias condiciones:

1. X, Y, Z deben rellenarse con 1, 4, 7
2. A, B, C deben llenarse con 1, 2, 3

Como X no puede ser 1 y A no puede ser 1, estas afirmaciones también son verdaderas:

1. Y o Z debe ser 1
2. B o C debe ser 1

Esto hace que el bloque 56Y,89Z,BCD no sea válido ya que debe contener dos 1, por lo tanto $N=49$ es imposible.

Sólo queda una pregunta:

¿Cuál es el máximo posible $N$ ? ¿Por qué?

Answer 1

Prueba de que $N=49$ es imposible:

+-------+---   1) +-------+      2) +-------+      3) +-------+
| 1 2 3 | X       |(1)2 3 |*1       | 1 2 3 |(7)      | 1 2 3 |(4)
| 4 5 6 | Y       |(4)5 6 |*4       | 4 5 6 | 1       |(4)5 6 | 7
| 7 8 9 | Z       |(7)8 9 |*7       |(7)8 9 | 4       | 7 8 9 | 1
+-------+---      +-------+         +-------+         +-------+ 
| A B C | D       | A B C | D       | A*B*C |*D       | A*B*C |*D  

El bloque de la primera cifra debe tomarse como nuestro "punto de partida". Como no hay otros números en el tablero, tenerlos ordenados no supone ninguna diferencia, por ahora. Ahora, hay 3 formas diferentes de llenar las fichas XYZ con 1 4 y 7, pero todas fallan. Ya que:

Caso 1: Obviamente, hay 3 colisiones.

Caso 2: BCD debe contener 237 en cualquier orden. Sin embargo, el 7 no puede estar en B ni en C porque colisiona con nuestra cuadrícula original. Y tampoco puede estar en D, porque está en la misma fila que la recién añadida.

Caso 3: similar al anterior, pero con 4.

Eso significa que no hay manera de tener esos 2 bloques (23X,56Y,89Z y 56Y,89Z,BCD) con éxito.

Por lo tanto, $N=49$ es imposible.

Answer 2

Usando la construcción de @Emisor, podemos reducir el límite superior a 39.

Primero un poco de preparación:

1. Utilizaré coordenadas cartesianas para referirme a las posiciones en el tablero, con (1,1) arriba a la izquierda y (9,9) abajo a la derecha.

2. Identificaré los bloques de solución por las coordenadas de su celda superior izquierda. Diré que el bloque está "anclado" en estas coordenadas. Los bloques obligatorios del Sudoku están anclados en (1,1), (1,4), (1,7), (4,1), (4,7), etc.

Si miramos con atención la construcción de @Emisor (en realidad: a la destilación que hace el OP de la misma), podemos ver que descarta no sólo el caso $N = 49$ sino cualquier configuración en la que cuatro celdas de un bloque de 2x2 sean todas anclas de solución. La construcción de Emisor conduce a este lema:

Lema 1: Sea (x,y) un ancla de solución. Supongamos que (x+1,y) y (x,y+1) también son anclas solución. Entonces (x+1,y+1) no puede ser un ancla solución. (No voy a copiar la prueba: Basta con observar que estas son las únicas suposiciones que se requieren).

Lema 2: En cualquier Grupo de celdas 2x2, como máximo tres pueden ser anclas de solución. Prueba: Basta con cambiar la orientación y aplicar la construcción del lema 1.

Así que consideremos los 49 posibles anclajes de la solución. Podemos asignar la mayoría de ellos a no se superponen Grupos de 2x2, cada uno de los cuales debe tener al menos una no-solución.

He aquí una sencilla asignación en grupos, construida en torno a los bloques obligatorios de la solución del Sudoku (que van en mayúsculas). Cada letra denota los miembros de un grupo.

        1 2 3   4 5 6   7 8 9
      +-------+-------+-------+
    1 | A a . | B b c | C . . |
    2 | a a . | b b c | c . . |
    3 | . . . | . . . | . . . |
      +-------+-------+-------+
    4 | D d . | E e f | F . . |
    5 | d d . | e e f | f . . |
    6 | g g . | h h j | j . . |
      +-------+-------+-------+
    7 | G g . | H h j | J . . |
    8 | . . . | . . . | . . . |
    9 | . . . | . . . | . . . |
      +-------+-------+-------+

Hay nueve grupos por encima, por lo que como máximo puede haber $49-9 = 40$ bloques de soluciones. Por ejemplo, $N_{max}$ <= 40. (Bajado a 39 abajo, sigue leyendo).

Notas:

1. El argumento es válido para cualquier grupo de 2x2, pero debemos elegir grupos no superpuestos para poder contar las no soluciones.

2. Obsérvese que varias celdas de anclaje potenciales (columna 3 y fila 3) no han sido asignadas a un grupo. Dado que las anclas de la solución deben estar en una cuadrícula de 7x7, dudo que haya una manera de encajar un décimo grupo de 2x2. (Sólo puede haber 3 grupos uno al lado del otro, pero yo no llamaría a eso una prueba completa).

3. Es muy posible que haya restricciones que se puedan expresar de diferentes maneras. Dado el número de puestos que no pertenecen a un grupo, estoy bastante seguro de que el verdadero máximo es inferior a 40. Esté atento a las actualizaciones (por mí o por otros :-)

Actualización 1

Basándonos en la disposición de los bloques anterior, podemos recortar uno más $N_{max}$ . Aunque en general no sabemos qué celda de un grupo será la no solución, sabemos que las letras mayúsculas deben anclar bloques de sudoku ya que nuestra cuadrícula es un sudoku válido. En particular, la posición (4,4), marcada por E arriba, debe anclar un bloque de solución. Esto significa que al menos una de las posiciones (3,3), (3,4) o (4,3) hace no anclar un bloque. Están marcados con @ abajo:

        1 2 3   4 5 6   7 8 9
      +-------+-------+-------+
    1 | A a . | B b c | C . . |
    2 | a a . | b b c | c . . |
    3 | . . @ | @ . . | . . . |
      +-------+-------+-------+
    4 | D d @ | E e f | F . . |
    5 | d d . | e e f | f . . |
    6 | g g . | h h j | j . . |
      +-------+-------+-------+
    7 | G g . | H h j | J . . |
    8 | . . . | . . . | . . . |
    9 | . . . | . . . | . . . |
      +-------+-------+-------+

Esto significa que $N_{max}$ puede ser como máximo $49 - 9 - 1 = 39$ .

Actualización 2

En un comentario En este caso, @rfg muestra cómo organizar 39 puntos de anclaje para que respeten la restricción de 2x2, e incluyan los 9 bloques básicos del Sudoku. Aquí está el boceto de @rfg; las X son las posiciones que se no puntos de anclaje. ( enlace imgur )

Por supuesto, esto no significa que haya un Sudoku real con estos 39 bloques de solución. Pero muestra que 39 es el límite de este enfoque: Si $N_{max}$ es, de hecho, inferior a 39, no se puede demostrar explotando únicamente esta restricción.

Answer 3

ACTUALIZACIÓN: Después de añadir la condición 3 (sólo 3 de cada 4 lugares en un cuadrado de 2x2 pueden ser un bloque, savile row + lingeling (un solucionador de SAT) demuestran que no hay ninguna solución con 34 o más bloques en unos 10 minutos. Esto, por supuesto, no proporciona ningún tipo de prueba agradable

He intentado modelar este problema en el Savile Row que puede generar entradas para los solucionadores SAT y el solucionador de restricciones Minion.

Esto puede recrear el N=33 casi instantáneamente, pero hasta ahora no ha encontrado nada para N > 33, después de un par de horas.

Pienso trabajar para mejorar mi modelo. Por el momento los únicos hechos no evidentes que estoy utilizando son:

• Al contar los cuadrados de 3x3 que satisfacen la condición, recuerda que los sub-bloques originales siempre lo hacen

• Podemos, sin pérdida de generalidad, asignar la primera fila a 1,2,...9

• En cualquier bloque de 2x2, a lo sumo 3 de los bloques con este cuadrado como su parte superior izquierda son bloques.

Aquí está el modelo de Savile Row, para el lector interesado (diseñado para encontrar > 33 casillas).

language ESSENCE' 1.0
letting   RANGE be domain int(1..9)
letting   LONGRANGE be domain int(0..9)
letting   VALUES be domain int(0..9)

find field: matrix indexed by [RANGE, RANGE] of RANGE

find squarecheck : matrix indexed by [LONGRANGE, LONGRANGE] of bool

find squares: int(34..100)

such that
  $ all rows have to be different
  forAll row : RANGE .
       allDiff(field[row,..]),

  $ all columns have to be different
  forAll col : RANGE .
     allDiff(field[..,col]),     

$ all 3x3 blocks have to be different
  forAll i,j : int(0..2) . (
    allDiff([field[row1+(i*3), col1+(j*3)] | 
             row1 : int(1..3), col1 : int(1..3) ])
    /\
    squarecheck[i*3,j*3] = true
  ),

  forAll i : int(0..8). forAll j : int(0..8).
    squarecheck[i,j]   + squarecheck[i+1,j]  +
    squarecheck[i,j+1] + squarecheck[i+1,j+1] <= 3,

  forAll i : int(0..9). forAll j : int(0..9) .
    squarecheck[i,j] =  allDiff([field[row1+i, col1+j] | 
             row1 : int(1..3), col1 : int(1..3) ]),

 sum(flatten(squarecheck)) = squares,

 forAll i : int(1..9). field[1,i] = i