Hoy estaba jugando una partida casual de Sudoku cuando vino un amigo y me preguntó: "¿Cuál es el juego de Sudoku más difícil posible?".
Mi respuesta: "Un rompecabezas Sudoku con la mínima cantidad de números iniciales donde el rompecabezas aún es resoluble".
Sin embargo, esto no me satisface porque quiero saber el mínimo real a la cantidad de casillas iniciales que puedo tener. Por supuesto, la posición también importa, así que asumiré que puedes colocar los números donde quieras para optimizar.
Lo más parecido que puedo hacer es analizar situaciones individuales para ver si tienen solución. Pero incluso cuando hago eso, no sé si hay una configuración con aún menos números de partida?
Q1: ¿Cuál es la cantidad mínima de números iniciales necesaria para que un juego de Sudoku se pueda resolver?
Q2: ¿Cómo definiría el juego "más difícil" de Sudoku?
7 votos
En realidad se sabe que la menor cantidad de números de partida es 17, no estoy seguro sin embargo, cómo se definiría difícil, podría ser un sudoku tal que es solucionable sólo si se utiliza un método en particular. Y eso tiene que ser un método difícil ..
0 votos
@windircurse Hm, ¿cómo probarías algo así?
9 votos
Se ha demostrado, con cálculos masivos de por medio, que se necesitan 17 cuadrados para forzar que sólo haya una solución. Sin embargo, estos rompecabezas no suelen ser muy difíciles. La dificultad depende de la colección de métodos que haya aprendido cada persona. Mientras tanto, cada rompecabezas puede ser resuelto por ordenador "backtracking"
0 votos
No estoy contento con tu respuesta porque no hay una buena manera de definir el concepto de orden parcial "más difícil". Además, los números iniciales mínimos podrían no implicar trivialmente que el relleno de las casillas no salga fácilmente, por ejemplo, podrías tener un puzzle mínimo con muchas casillas con muy pocas posibilidades.
0 votos
Después de leer estos comentarios, he editado la pregunta para incluir cuál podría ser el "juego de Sudoku más difícil".
1 votos
Debería retractarme de lo que dije en parte, lo que no me gusta es la pregunta en sí. Sólo tiene sentido si uno puede formalizar "más difícil" aquí. Si uno lo hace, tal vez sea incluso trivial responderla. Sin definirlo, la pregunta no es más que una sarta de palabras sin sentido.
0 votos
@GitGud ¿Pero qué haría que un juego de Sudoku fuera "difícil"? Si nos fijamos en lo que ha dicho Will Jagy, "difícil" probablemente se basa en los métodos necesarios para resolver el rompecabezas, y eso no parece ser una gran definición de "difícil", formalmente. Quizá la pregunta sea demasiado amplia para responderla. De todos modos, gracias por la aportación.
2 votos
Debo subrayar que la gente ha inventado muchísimas estrategias para resolver, los autores más responsables intentan ceñirse a algo que podría hacer un ser humano. En cualquier caso, ninguna colección de estrategias humanas razonables puede resolver todos los rompecabezas. Como ya he dicho, el backtracking puede resolverlos todos, y en las Notices apareció un artículo que adaptaba el backtracking para humanos utilizando lápices de colores. Sin embargo, para mí no es muy divertido.
1 votos
@SimpleArt "Duro" y "más duro/más difícil" son dos conceptos muy diferentes. El primero es un adjetivo. Hay pocas esperanzas de que alguien pueda dar una definición matemática que lo englobe adecuadamente. El segundo es (o más bien espera ser) un orden parcial y, aunque no es tan difícil de formalizar como "duro", su formalización sigue siendo poco prometedora. En su pregunta se refería al "más difícil". "Hardest" es el máximo del orden parcial para ser "harder" y no tiene nada que ver con el adjetivo "hard".
1 votos
Mi definición de difícil es que usando las heurísticas comunes usadas para acelerar el backtracking fallará : la primera heurística es listar cuales son los posibles valores en cada celda, y elegir el más restringido La otra heurística común, un paso más allá, consiste en elegir en su lugar el valor más alto posible. que limita variable primero : esto es heurísticamente una buena idea ya que al probar un valor para una variable altamente restrictiva, si el valor no es correcto deberíamos ser capaces de detectarlo muy pronto... @SimpleArt
1 votos
Entonces debería echar un vistazo a El sudoku como problema de restricciones que trata del muy general wiki/Programación_limitada un subconjunto especializado (y de nivel superior) de SAT . Con ellos puedes resolver cualquier puzzle con un solo solucionador, pero este solucionador tendrá que realizar backtracking (probar un valor y ver si funciona, recursivamente) y esto tendrá una complejidad exponencial ( ver es.wikipedia.org/wiki/P_versus_NP_problem )
0 votos
No estoy muy familiarizado con las definiciones exactas, pero algunos solucionadores empedernidos miden la dificultad de un rompecabezas dado (o, más exactamente, de una prueba dada de la unicidad de la solución de un rompecabezas dado) en términos de la longitud de las cadenas que necesitan estudiar para poder hacer deducciones (como eliminar un número determinado como posibilidad de una celda determinada). Los eslabones de esas cadenas son proposiciones "atómicas" sobre la verdad de la aparición de un número dado (o un grupo dado de números) en una celda dada (o un grupo dado de celdas).
0 votos
(cont.) La cifra de dificultad global de una solución es entonces una suma ponderada de las longitudes de esas cadenas, teniendo las cadenas más largas pesos más altos. Sin duda no es la única forma de medir la dificultad de un sudoku.
0 votos
Los aficionados a los rompecabezas utilizan Sudoku Explainer u otras herramientas similares para definir la dificultad de los sudokus. Estas herramientas resuelven los Sudokus mediante argumentos lógicos que utilizan los humanos, no retrocediendo.