¿Qué tan difícil es resolver un Sudoku?

Answer 1

Hay dos formas de entender su pregunta.

1. ¿Qué tan difícil es para una computadora, por cualquier método posible? Lo relevante aquí es el tiempo de resolución. Como se sabe que Sudoku (n) es NP-completo, no existe una solución polinómica. Para el Sudoku estándar (9), el algoritmo más rápido conocido es la búsqueda en profundidad. Es muy rápido: cualquier rompecabezas se puede resolver en una fracción de segundo (y los programas de código abierto C para esto están ampliamente disponibles).
2. ¿Qué tan difícil es para un humano? Ahora, todavía hay varias formas de entender la pregunta. Pero generalmente se requiere una solución humana para satisfacer una condición adicional: debe ser “puramente lógica” o “basada en patrones”. Esto significa que cada paso (eliminación / aserción de un candidato) en el proceso de resolución debe estar justificado por alguna “regla de resolución” del tipo: condición-patrón ==> eliminación (o aserción) de un candidato. En lo que sigue, me atendré a esta vista y consideraré solo los acertijos 9 × 9 estándar.

Los acertijos que puedes encontrar en los periódicos dan una idea muy parcial de cuán compleja puede ser una solución “lógica”. En comparación con los acertijos conocidos más difíciles, las graduaciones habituales (fácil, moderada, … dura, súper dura, diabólica, diabólica, …) son como un grano de polvo en el primer paso hacia la cima del Everest. (Existen diferentes medidas posibles de complejidad, pero he demostrado * que están fuertemente correlacionadas, por lo que la oración anterior es válida, cualquiera de las que considere).

Ahora, también está la cuestión de qué patrones particulares se permiten en el proceso de resolución. No hace falta decir que hay enfoques muy diferentes y si alguna vez echas un vistazo a los foros de Sudoku, verás que han sido objeto de acalorados (pero rara vez esclarecedores) debates.

Desafortunadamente, muy pocos conjuntos de reglas se han estudiado sistemáticamente con respecto a su poder de resolución (de hecho, el único estudio que conozco es el mío *). La mayoría de las reglas recomendadas por los “expertos en sudoku” solo pueden resolver una pequeña fracción de todos los acertijos. Para el resto de los rompecabezas, es necesario algún tipo de regla de cadena; He definido varios tipos de reglas de cadena y he demostrado * que una de ellas (trenzas B) puede resolver todos los acertijos 9 × 9 conocidos (y que es muy poco probable que se pueda encontrar un acertijo 9 × 9 fuera de su alcance) . Las reglas en este conjunto proporcionan una calificación lógica de cualquier rompecabezas de 9 × 9, más preciso que mi metáfora del Everest.

(* en mis libros “La lógica oculta del Sudoku” o el más reciente “Satisfacción de restricciones basadas en patrones y acertijos lógicos”)

Answer 2

¿Qué tan difícil es leer un libro? ¿Un libro para niños con palabras de 3 letras o Finnegans Wake ?

Personalmente, he creado libros electrónicos de rompecabezas de Sudoku estándar con rompecabezas para principiantes, fáciles, medios y difíciles (por ejemplo, Sudoku de Fire Easy # 1). He visto rompecabezas más fáciles que mis rompecabezas para principiantes y mucho más difíciles que mis rompecabezas difíciles.

También he creado libros electrónicos de Sudoku 8 y Puzzazz publica Sudoku Tres en línea, ambas variantes específicamente diseñadas para ser más fáciles (la mayoría de las variantes de Sudoku son más difíciles).

En resumen, un rompecabezas de Sudoku es tan difícil de resolver como quieres que sea. Simplemente elige el acertijo correcto.

Answer 3

Creo que la respuesta de Roy (o específicamente, la parte ‘en resumen’ al final 🙂) es la respuesta perfecta. Incluso en las competiciones nacionales e internacionales de Sudoku, nunca se ha dado el caso de que todos los Sudokus tengan la misma dificultad, algunos son fáciles, otros son medios, otros son difíciles. Luego hay variaciones de Sudoku que también tienen diferentes grados de dificultad.

Probablemente podría resolver el Sudoku más fácil en un minuto y no estar cerca de las posiciones más altas, y luego resolver el Sudoku más difícil en 4 minutos y estar entre los 3 primeros, así que afortunadamente para mí, las rondas son una mezcla de fácil, medio y difícil, para que pueda aprovechar mis puntos fuertes, resolver los difíciles y obtener los valores de puntos altos asignados a ellos 🙂 Pero incluso aquí es subjetivo: tal vez uno de ellos usa la estrategia del ala X y el otro tiene un Y -Alta pero también un atajo de rectángulos único en alguna parte: generalmente soy malo para detectar alas y otras cosas, pero soy excelente para detectar rectángulos únicos, por lo que probablemente lo pasaré muy bien con este último a pesar de que se considera muy difícil.

Al final, se trata de conocer las técnicas y, lo que es más importante, cómo las aplica, y qué tan capacitado y experimentado está para detectar dónde y cuándo aplicarlas. Y todo esto difiere de persona a persona, así como de Sudoku a Sudoku.

Answer 4

Resolver un [math] n ^ 2 \ times n ^ 2 [/ math] El tablero de Sudoku es NP-hard: no se conoce un método de resolución que sea tiempo polinómico en [math] n [/ math]. Ver NP-completitud de Sudoku.

En lo que respecta al rompecabezas de 9 × 9, la dificultad varía de fácil a diabólica dependiendo de cuántos y qué cuadros se llenan y con qué.

Answer 5

Depende de la dificultad del rompecabezas. Algunos son fáciles y se pueden completar varían rápidamente, lo que significa en un par de minutos. Algunos son difíciles y nunca terminé, algunos lo intenté.

De todos modos, aquí hay un enlace a mayo acaba de lanzar el juego Sudoku para dispositivos Android

Sudoku Offline and free – Aplicaciones de Android en Google Play

lo siento si cae como spam, pero estoy tratando de que la gente sepa de su existencia 🙂

Answer 6

Depende de la dificultad del rompecabezas. Los hago durante toda la semana en el periódico. Lun. toma <5 minutos y se vuelven progresivamente más difíciles hasta el sol. lo que puede llevar días resolver.