¿Todos los rompecabezas de sudoku se pueden resolver mediante deducciones lógicas o algunos requieren una suposición en algún momento?

Answer 1

Todos los rompecabezas de Sudoku se pueden resolver solo mediante deducciones lógicas, sin adivinar. Algunos rompecabezas de Sudoku difíciles pueden requerir técnicas deductivas que no conoces. Algunos rompecabezas de Sudoku muy difíciles pueden requerir técnicas que son tan complicadas que ningún humano puede hacerlo sin tomar notas extensas. Y es posible que haya algunos acertijos de Sudoku que requieran técnicas que aún no conocemos; ese acertijo no se consideraría legítimo hoy en día.

En pocas palabras, si no es solucionable, entonces no es un rompecabezas. Déjame dar un ejemplo. Complete lo siguiente:

“Eso ___”

Esto tiene una solución única. ¿Qué es? Spoiler: es Catch-22 . Complete con el texto completo de Catch-22 , comenzando con “Fue amor a primera vista”. Si pensabas que comenzó “Fue una noche oscura y tormentosa” de Paul Clifford o A Wrinkle in Time , mis disculpas, lo resolviste incorrectamente. Se podría argumentar que los Sudokus son diferentes, que, por ejemplo, el “rompecabezas” de Escargot mencionado por David Spencer es válido porque solo tiene una solución, y que mi ejemplo tiene múltiples soluciones (un rompecabezas válido tiene una solución única o una conocida , generalmente indicado, número de soluciones; las preguntas abiertas pueden ser divertidas pero no son acertijos). No hay problema, solo cambiaré mi rompecabezas:

“Estaba ___ carpa ___ apagado”.

Ahora (probablemente) tiene una solución única. Todavía no es un rompecabezas válido. Tal vez parece un rompecabezas y puedo afirmar que es un rompecabezas, pero eso no lo convierte en un rompecabezas, porque no tiene solución.

Merriam-Webster define el rompecabezas como “una pregunta o problema que requiere pensamiento, habilidad o inteligencia para ser respondido o resuelto; algo o alguien que es difícil de entender”. Si no se puede responder, resolver o comprender, entonces, por definición , no es un rompecabezas.

En resumen:

1) Hay muchos millones de conjuntos de números que parecen ser acertijos de Sudoku, y que coinciden exactamente con un conjunto final de números de acuerdo con las tres reglas de los acertijos de Sudoku, que son interesantes sobre una base teórica, e incluso podrían ser acertijos de Sudoku válidos en el futuro a medida que se aprendan nuevas técnicas. Pero estos conjuntos de números no son acertijos válidos hoy.

2) ¿Podría un solucionador determinado tener que adivinar para resolver un rompecabezas en particular? Sí, si el rompecabezas requiere técnicas que no conocen.

Answer 2

Tres formas de interpretar su pregunta, la más fácil primero:

Por definición, un sudoku adecuado solo tiene una solución, por lo que sí, en principio se puede deducir.

Uno puede construir un sudoku incorrecto que tenga más de una solución. Entonces no , obviamente tienes que adivinar, pero ese no es un verdadero sudoku.

¿Para resolverlos en la práctica? Como alguien que lo ha hecho razonablemente bien en competiciones de sudoku, creo que estoy calificado para responder.

Para la mayoría de los niveles de dificultad, cualquier cosa por debajo de “malvado” o “extremadamente difícil”, no vale la pena adivinar. Puede deducirlo todo más fácilmente de lo que puede dar marcha atrás a las malas conjeturas.
Posiblemente tenga que encontrarlo falso y retroceder: si solo escribe “5” en un cuadrado probable sin forma de recuperarlo, es probable que obtenga un rompecabezas fallido.

Esto depende de lo que haga su aplicación de rompecabezas con malas conjeturas, por supuesto. Algunas aplicaciones señalan inmediatamente conjeturas erróneas y algunas le permiten retroceder más fácilmente que otras. Para aquellos que vale la pena adivinar más fácilmente. Incluso entonces, desea ver todo lo que puede hacer con cuadrados de 2 vías antes de adivinar. Eso es un poco aparte de su pregunta: usted preguntó si era necesario adivinar, no si era conveniente.

Y luego hay niveles de dificultad más altos. Ahí te encuentras en situaciones en las que ninguna lógica de superficie sobre los cuadrados de 2 y 3 vías progresa. Tienes que probar una hipótesis. Entonces no , a veces tienes que adivinar. Yo mismo, elijo un probable cuadrado de 2 vías y lo intento en ambos sentidos, haciendo una notación de lápiz particular en cada cuadrado que deduzco de cada suposición, para que pueda retroceder si encuentro una contradicción.

Ahora que he dicho “sí” y “no”, siento la necesidad de resolver la paradoja. La cuestión es que “adivinar” es otra forma de decir “hacer una hipótesis y probarla”.
Generar una hipótesis, probarla y dar marcha atrás es nuestro viejo amigo prueba por contradicción, y la prueba por contradicción es parte de la lógica. Entonces “adivinar” es parte de la deducción lógica, por lo que “sí y no” no es realmente una contradicción.

tl; dr: sí y no, y adivinar no es necesariamente lo contrario de la lógica.

Answer 3

Esta es una pregunta difícil de responder porque las fuentes de Sudoku pueden variar mucho. Si descarga un Sudoku aleatorio de Internet, es probable que tenga un Sudoku elegantemente hecho a mano por un autor muy capaz y experimentado como lo es tener un Sudoku generado aleatoriamente en un generador mal codificado.

Si la fuente es un buen autor o un buen generador, el Sudoku se resolverá mediante deducciones lógicas. Puedo recomendar algunos sitios donde solo encontrarás Sudokus.

Si la fuente es un autor inexperto o un mal generador, el resultado puede ser desde un Sudoku completamente ilógico hasta algo peor como un Sudoku sin solución o un Sudoku con múltiples soluciones.

Muy recientemente, un amigo me mostró un Sudoku que le dieron en un restaurante que tiene resolución de acertijos, y me dijo que el propietario insiste en que se trata de un ‘Sudoku muy difícil que nadie ha podido descifrar todavía’. Lo miré y había una razón simple por la que nadie podía descifrarlo: no había una solución válida. No podría haber 9 en toda la columna 4, lo que viola las reglas de inmediato. Es probable que el restaurante haya descargado aleatoriamente el rompecabezas de Internet o haya descargado aleatoriamente un generador defectuoso.

Entonces, la respuesta más simple a su pregunta es la fuente y si obtiene el Sudoku de una buena fuente, será solucionable solo por deducciones lógicas.

Answer 4

Un rompecabezas de Sudoku oficial genuino y documentado tendrá solo una solución única, se resolverá solo a través de lógica y técnicas que no implican ninguna adivinanza.

Algunas personas consideran que “Adivinar” y “Retroceder” como una técnica de resolución … Sí, resolverá el acertijo, pero vencerá la definición básica de que solo la lógica “SIN ADORNOS” podrá resolver el acertijo. X-Wing, Swordfish y Foced Chain son las últimas técnicas para resolver un Sudoku experto además de otras 6 técnicas básicas.

“Bifurcación” es otro término utilizado para adivinar … Y tampoco es legítimo.

Si no puede con absoluta garantía colocar un número en la cuadrícula, entonces está adivinando y eso no se considera una solución de sudoku. Todas las técnicas de resolución de Sudoku que se basan en la lógica están documentadas y permitidas para resolver el rompecabezas.

Si su aplicación le permite dar marcha atrás o adivinar, desactive esas opciones e intente resolverlas solo con una solución lógica. Esa es la mejor manera de jugar y dominar el Sudoku.

Answer 5

Creo que depende de la dificultad. En su mayor parte, requiere un razonamiento deductivo.

Sin embargo, algunos requieren que adivine los primeros números y luego realice un razonamiento deductivo si su conjetura es correcta. Por ejemplo, en un sudoku en blanco dado con solo 3 números dados, requeriría que adivine, ya que no será deducible. Pero dados los números aleatorios iniciales que escribió, será deducible después de haberlo hecho. Después de un tiempo, se encontrará con un cuello de botella y luego tendrá que retroceder.

El Sudoku más difícil le permite adivinar (dar un número aleatorio inicial) y luego le permite dar marcha atrás, que está modelado a partir de una solución de problemas de la vida real. es decir, en algún momento necesita volver sobre algunos de sus pasos hasta que haya acertado.

No creo en el Sudoku puramente deducible, ya que es fácil (y da muchos números iniciales) y no refleja la resolución de problemas de la vida real a través de prueba y error (filosóficamente, eso es) como lo hace la mayoría de los científicos.

Answer 6

No, aunque la gran mayoría puede, y todo lo que encontrará en una lata de periódico. Algunos métodos son suficientes para la mayoría de los acertijos: al observar la lista de técnicas en Sudoku Techniques, las técnicas fáciles, medias y avanzadas resolverán casi todos los acertijos que verá publicados, aunque he oído hablar de un acertijo en una revista que requería una X -Ala (la primera técnica maestra).

Sin embargo, todos estos métodos fallan para algunos sudokus, que no se publicarán para que la gente realmente los resuelva. El excelente solucionador en Sudoku Solver de Andrew Stuart le permite ingresar un sudoku y hacer clic en “Dar un paso” para ver la próxima deducción que se puede hacer y una explicación. A la izquierda, debajo de “Elige un ejemplo aquí”, ve a Escargot. Este es un rompecabezas famoso y difícil, y puedes ver que si das un par de pasos en Escargot, cada estrategia falla. Incluso utiliza algunos métodos (como Rectángulos únicos) que, de hecho, suponen que los acertijos solo tienen una solución, pero aún se requiere retroceder.

Answer 7

Mi respuesta incompleta se basa en mi libro “Satisfacción de restricciones basadas en patrones y rompecabezas lógicos” (PBCS) donde puede encontrar todos los detalles (la primera edición está disponible gratuitamente en mi sitio web o en arxiv.org).

Permítanme primero especificar que a continuación, un rompecabezas de Sudoku significará uno válido, es decir, uno con una y solo una solución. También hablaré solo de acertijos 9 × 9. Para extensiones más allá de tales condiciones, vea el libro.

He definido una clasificación de todos los acertijos de acuerdo con la profundidad de prueba y error que requiere su solución (consulte la definición precisa de T&E (n) en PBCS).

Parece que todos los acertijos conocidos de 9 × 9 son:

• ya sea en T&E (0), es decir, solucionable por solteros desnudos y ocultos,
• o en T&E (1), que he demostrado que es equivalente a ser solucionable por trenzas, un patrón de cadena definido en términos lógicos puros (ver PBCS),
• o en T&E (2), que es equivalente a ser solucionable por las trenzas B, un patrón de cadena mucho más complejo con sub-trenzas incrustadas, pero aún definido en términos lógicos puros (ver PBCS).

De ahí que mi T&E (2) conjetura que todos los rompecabezas de 9 × 9 están en T&E (2).

Sigue siendo una conjetura porque nadie sabe con certeza que no hay acertijos 9 × 9 desconocidos que requieran más que T&E (2). Sin embargo, esta conjetura está muy fuertemente respaldada por los siguientes hechos:

• solo hay 1 de cada 30,000,000 rompecabezas que requieren T&E (2),
• He definido una subclasificación de T&E (2): B0B, B1B, B2B, … en términos de las sub trenzas más grandes requeridas en las trenzas B utilizadas para resolver un rompecabezas; Después de años de búsqueda de los rompecabezas “más difíciles” por una gran comunidad de Sudoku, todos los rompecabezas CONOCIDOS están en B0B o B1B … o B7B y se sabe que solo un puñado de rompecabezas está en B7B, lo que hace que sea muy poco probable que haya un rompecabezas en se descubrirá un BnB más grande, y mucho menos más allá de T&E (2).

Tenga en cuenta que permitir patrones adicionales, por ejemplo, los subconjuntos clásicos (desnudos, ocultos o súper ocultos) o patrones más exóticos, no cambia mucho las clasificaciones anteriores en la media (ver PBCS).

Entonces, mi respuesta final es: TODOS LOS acertijos de Sudoku 9 × 9 conocidos se pueden resolver mediante lógica pura constructiva, PERO

• no tenemos pruebas formales de que este resultado pueda extenderse a TODOS los acertijos, a pesar del fuerte respaldo de mi conjetura de T&E (2),
• para (los relativamente pocos) rompecabezas en T&E (2), esto requiere patrones de cadena complejos (trenzas B) y probablemente a nadie le gustaría leer una prueba de resolución.

Si consideramos rompecabezas más grandes, una gran proporción de ellos requiere T&E (3) o más. Se pueden definir patrones de cadena aún más complejos, pero serían totalmente ilegibles.

Answer 8

Cada rompecabezas de sudoku construido correctamente tendrá solo una solución, independientemente de si se ha adivinado o no.

Es solo una cuadrícula de 9 × 9 de 81 dígitos, valor 1 a 9, que debe obedecer 3 reglas simples para evitar duplicados en: 3 × 3 subcuadrícula, filas y columnas

La dificultad para resolver depende de factores como cuántos dígitos se han eliminado y cómo se relacionan entre sí los dígitos iniciales restantes.

Con esta información, un verdadero sudoku debe resolverse mediante una serie de deducciones lógicas en lugar de suponer conjeturas.

Completo el sudoku Super Fiendish en el Times solo por deducción, en la mayoría de las ocasiones. Sin embargo, otro tabloide diario, el Metro, tiene 3 sudokus por día, el más difícil de los cuales se llama “Desafiante” y creo que una gran cantidad de estos son insolubles utilizando métodos deductivos. A menudo se reduce a un número que va en una de dos casillas y se debe hacer una suposición de 50/50. A veces trato de jugar el juego adelante proyectando algunos movimientos aguas abajo según mi elección, pero eso solo puede llegar tan lejos. Entonces puedo tener suerte y completar o no, 50% de posibilidades. Y si tengo que hacer 2 conjeturas, normalmente renuncio ya que solo tengo un 25% de posibilidades de completar pero al menos tener la comodidad de que no es un sudoku adecuado 😉

Answer 9

Todavía no he visto un rompecabezas que no se pudo resolver mediante la deducción, pero lo más difícil en mi experiencia ha requerido el uso de notas, que algunas personas (no yo) consideran un truco.

La respuesta de David Spencer es buena, y en ella hace referencia al excelente Solucionador de Sudoku de Andrew Stuart. Casualmente, Andrew Stuart proporcionó los juegos que utilizamos en nuestra aplicación de sudoku, y hasta la fecha nunca he tenido que adivinar un rompecabezas: Sue Doku

Answer 10

Sí, pero debes ser muy cuidadoso y lógico. Considerará varios cuadros, filas y columnas a la vez. Es increíblemente difícil y consume mucho tiempo. Intenta bajo tu propio riesgo.