Solucionador de Sudoku

El Sudoku es un juego de lógica que consiste en rellenar una cuadrícula 9x9 con los números del 1 al 9. Cada número debe aparecer una y solo una vez en cada fila, cada columna y cada uno de los 9 bloques 3x3.

Existen variantes con otros tamaños o con símbolos (letras, iconos). La estructura matemática sigue siendo idéntica: se trata de un problema de satisfacción de restricciones en el que cada símbolo debe respetar reglas de unicidad local.

La cuadrícula puede rellenarse copiando y pegando una secuencia de 81 caracteres (números o símbolos), o introduciendo directamente los valores en las casillas.

Se aceptan los números $ 1 $ a $ 9 $. Para las variantes de tipo Wordoku, también pueden utilizarse letras, siempre que se empleen 9 símbolos distintos.

El programa resuelve el Sudoku 9x9 como lo haría un humano, combinando deducciones lógicas.

— Cálculo de candidatos: para cada casilla vacía, dCode determina el conjunto de valores posibles compatibles con las restricciones de fila, columna y bloque.

— Único valor posible: si una casilla solo tiene un candidato, ese valor se valida.

— Única casilla posible: si, para un número dado, solo una casilla de una fila, columna o bloque puede contenerlo, ese valor se valida.

En una cuadrícula clásica 9x9, un bloque (también llamado región o grupo o sector o subcuadrícula) es un cuadrado 3x3. Hay 9 bloques en total.

dCode calcula todas las soluciones del sudoku, y no solo la primera. Para verificar un sudoku casero, el solucionador podrá confirmar que existe una sola y única solución.

La forma moderna del Sudoku fue publicada en 1979 por Howard Garns en la revista estadounidense Dell con el nombre Number Place.

El juego fue posteriormente popularizado en Japón en los años 1980 por la empresa Nikoli, que le dio el nombre Sudoku, contracción de Sūji wa dokushin ni kagiru, que significa los números deben permanecer únicos.

Una sola fila puede formarse de $ 9! $ (factorial de 9) maneras diferentes, al igual que las columnas, pero el sudoku completo tiene un número de posibilidades muy inferior a $ 9!^9 $, ya que algunas permutaciones pueden conducir a cuadrículas idénticas. El número total de cuadrículas es $ 9! \times 72^2 \times 2^7 \times 27704267971 = 6670903752021072936960 $ combinaciones (resultado demostrado en 2005).

Para que un sudoku tenga una única solución, debe tener al menos 17 casillas prellenadas de las 81 totales. Gary McGuire y su equipo demostraron esto here utilizando un algoritmo para realizar una búsqueda sistemática por ordenador. Primero catalogaron las 5 472 730 530 cuadrículas de sudoku distintas. Luego crearon un programa para verificar si los sudokus con 16 casillas prellenadas tenían una solución única. Su búsqueda exhaustiva no encontró ningún sudoku con solo 16 casillas prellenadas que tuviera una solución única, confirmando así el número mínimo de 17 casillas prellenadas necesarias.

Manteniendo las reglas del sudoku NxN que requieren utilizar los N caracteres en cada fila y cada columna, entonces es imposible respetarlas si el sudoku no es cuadrado.

Sin embargo, algunas variantes del sudoku cuadrado utilizan bloques interiores no cuadrados (ver sudoku 6x6, sudoku 7x7 o sudoku 8x8)