Sudoku 17 pistas Malvado

Cómo jugar Sudoku 17 pistas

Sudoku es un rompecabezas de colocación de números basado en la lógica. El objetivo es llenar una cuadrícula de 9x9 con los números del 1 al 9, de modo que cada fila, columna y subcuadrícula de 3x3 contenga los nueve números exactamente una vez.

En 2009, Gary McGuire y su equipo demostraron que cualquier Sudoku con 16 pistas debe tener al menos dos soluciones. Lo hicieron utilizando una técnica llamada "patrones muertos".

Un patrón muerto es una configuración de Sudoku que tiene dos o más soluciones posibles. McGuire y su equipo descubrieron que cualquier Sudoku con 16 pistas debe contener al menos un patrón muerto. Por lo tanto, estos acertijos deben tener al menos dos soluciones.

Este resultado tiene varias implicaciones. En primer lugar, significa que no existe un Sudoku de 16 pistas con una solución única. En segundo lugar, significa que cualquier Sudoku de 16 pistas se puede resolver de múltiples maneras. En tercer lugar, significa que hay un número infinito de Sudokus de 16 pistas.

Aquí hay una explicación más técnica de la prueba de que los Sudokus deben tener al menos 17 pistas para tener una solución única:

La prueba comienza considerando un Sudoku con 16 pistas. Podemos pensar en este rompecabezas como un conjunto de restricciones sobre los números que se pueden colocar en los cuadrados vacíos.

Luego podemos utilizar una técnica llamada "retroceso" para intentar encontrar una solución al rompecabezas. El retroceso es un algoritmo recursivo que prueba todas las combinaciones posibles de números en los cuadrados vacíos hasta encontrar una solución.

Si hay una solución única al rompecabezas, retroceder eventualmente la encontrará. Sin embargo, si hay varias soluciones, es posible que retroceder nunca encuentre una solución.

McGuire y su equipo utilizaron el retroceso para demostrar que si hay un Sudoku de 16 pistas con una solución única, entonces debe haber una manera de iniciar el algoritmo de retroceso de tal manera que siempre encuentre la solución.
Luego demostraron que esto no es posible. Lo hicieron construyendo un conjunto de 16 pistas que conducen a un patrón muerto. Este patrón muerto significa que hay dos posibles soluciones al rompecabezas y no hay forma de iniciar el algoritmo de retroceso de tal manera que siempre encuentre la misma solución.
Este resultado muestra que cualquier Sudoku de 16 pistas debe tener al menos dos soluciones.