¿Número mínimo de pistas para especificar completamente cualquier sudoku?

9

Sabemos por este documento que no existe un rompecabezas que pueda resolverse comenzando con 16 o menos pistas, pero implica que existe un rompecabezas que puede resolverse a partir de 17 pistas. ¿Se pueden especificar todos los rompecabezas de sudoku válidos en 17 pistas? Si no, ¿cuál es el número mínimo de pistas que pueden especificar completamente cada rompecabezas válido? Más formalmente, ¿existe un rompecabezas de sudoku válido (o, supongo que sería un conjunto de rompecabezas) que no se puede resolver de manera única a partir de solo 17 pistas? Si es así, ¿cuál es el número mínimo de pistas, , de modo que cada rompecabezas de sudoku válido pueda especificarse de manera única en o menos pistas?CC

Kevin
fuente

Respuestas:

2

Dado que la permutación de dos filas dentro de un solo bloque de un sudoku completo válido produce otro sudoku completo válido, puede tomar cualquier tablero completo (81 pistas) y eliminar las dos primeras filas (81-18 = 63 pistas), lo que le dará Un sudoku incompleto con dos soluciones. Tenga en cuenta que incluso si elimina todos menos uno de los 18 números allí, la solución se determina inmediatamente de manera única (ya que no puede repetirse ningún número en la misma columna).

Otra operación que produce otro sudoku completado es aplicar una permutación de . Si toma una permutación que es una transposición (permuta dos elementos, manteniendo el otro fijo), nuevamente, como antes, puede eliminar todas las apariencias de esos dos elementos y tiene un sudoku incompleto con dos posibles soluciones y 63 pistas. Nuevamente, si no elimina los 18 números, la solución será única.{1,,9}

De las seis operaciones elementales que producen un sudoku completo (ver aquí ), estas dos son las que pueden involucrar la menor cantidad de elementos, por lo que diría que es un límite superior para lo que está buscando. Sé que esto no responde exactamente a su pregunta, pero la idea general de eliminar conjuntos de posiciones que producen dos soluciones diferentes podría ser un buen punto de partida.C=63

Janoma
fuente
1

La menor cantidad de pistas requeridas para un Sudoku adecuado es 17, pero no todas las cuadrículas completas se pueden reducir a un Sudoku de 17 pistas adecuado. Se han encontrado alrededor de 49,000 Sudokus únicos (no equivalentes) con 17 pistas. (Un Sudoku adecuado solo tiene una solución).

Se cree que la mayoría de las pistas en un Sudoku mínimo son 40 (se sabe que existen dos), pero no se ha demostrado si este es el máximo. (mínimo significa que si se elimina alguna pista, el Sudoku tendría más de una solución y, por lo tanto, no sería un Sudoku adecuado)

(Esta información es de Wikipedia, de la cual estas declaraciones están bien referenciadas).

tomoka kazuki
fuente
Me interesa saber si 41 es un límite superior probado (como ). N2
rus9384
No he visto eso probado en ningún artículo. Curiosamente, casi todo el trabajo para encontrar un Sudokus mínimo "h" de alta pista parece ser realizado por una búsqueda de Sudokus conocidos, y modificarlos para aumentar iterativamente "h". El trabajo para encontrar los rompecabezas mínimos de 40 pistas produjo una base de datos de más de 6,500,000,000 de otros rompecabezas mínimos de pistas altas. Excepto por problemas triviales, casi no he visto ninguna investigación rigurosa por ningún otro medio que no sea "buscar". Pero tu propuesta es interesante.
tomoka kazuki
¿Podría agregar las citas aquí, por favor? O al menos un enlace a la página relevante de Wikipedia.
David Richerby
Esta información es del artículo de Wikipedia "Matemáticas del Sudoku", sección "Número máximo de datos". La referencia citada (para el descubrimiento del primer Sudoku mínimo de 40 pistas) es: forum.enjoysudoku.com/high-clue-tamagotchis-t30020-135.html La información clave es la hoja 10, pero la información relacionada es antes y después de la hoja 10.
tomoka kazuki
0

Este Sudoku tiene 77 pistas y, sin embargo, tiene múltiples soluciones (2). Puede usar 7-4 en la fila superior y 4-7 en la otra o usando 4-7 en la parte superior y 7-4 en la parte inferior. Este rompecabezas de Sudoku en particular necesita 78 pistas para tener una solución única.ingrese la descripción de la imagen aquí

Nicomal
fuente
Este es un buen punto, pero creo que no es exactamente la pregunta que se hace, que se trata de un número mínimo de pistas para especificar el rompecabezas si puedes elegir las pistas estratégicamente
6005
Creo que es una buena respuesta, pero sería bueno agregar a esta respuesta (1) una nota de por qué esto es un poco diferente a la pregunta formulada, (2) convertir la imagen borrosa en una tabla en texto y / o una explicación
6005