Sudoku es un pasatiempo que se popularizó en Japón en 1986, aunque es originario de Suiza, y se dio a conocer en el ámbito internacional en el 2005. El objetivo es rellenar una cuadrícula de 9×9 celdas (81 casillas) dividida en subcuadrículas de 3×3 (también llamadas "cajas" o "regiones") con las cifras del 1 al 9 partiendo de algunos números ya dispuestos en algunas de las celdas. No se debe repetir ninguna cifra en una misma fila, columna o subcuadrícula.
Método de resolución
La estrategia para resolver este rompecabezas se puede considerar como la combinación de tres procesos: escaneo, marcado y análisis.
Escaneo
El escaneo se realiza desde el principio y periódicamente, durante toda la resolución. El escaneo puede ser ejecutado varias veces entre periodos de análisis. El escaneo consta de dos técnicas básicas: trama cruzada y recuento, que pueden usarse alternativamente.
Trama cruzada: se trata del escaneo de filas (o columnas) para identificar qué línea en una región particular puede contener un número determinado mediante un proceso de eliminación. Este proceso se repite entonces con las columnas (o filas). Para obtener resultados más rápidos, los números son escaneados de forma ordenada, según su frecuencia de aparición. Es importante realizar este proceso sistemáticamente, comprobando todos los dígitos del 1 al 9.
Recuento: 1-9 por regiones, filas y columnas para identificar números perdidos. El recuento basado en el último número descubierto puede aumentar la velocidad.
Marcado
El escaneo viene a interrumpirse cuando no pueden descubrirse nuevos números. En este punto es necesario centrarse en algún análisis lógico. La mayoría encuentra útil guiar este análisis mediante el marcado de números candidatos en las celdas vacías. Hay dos notaciones populares: subíndices y puntos. En la notación de subíndice, los números candidatos se escriben en pequeño en las celda. La segunda notación es un patrón de puntos con un punto en la esquina superior izquierda representando un 1 y un punto en la esquina inferior derecha representando un 9.
Análisis
Hay dos aproximaciones principales - eliminación y "y-si"
Eliminación: el progreso se realiza mediante la sucesiva eliminación de números candidatos para una o más celdas, hasta dejar sólo una elección. Después de lograr cada respuesta, debe realizarse un nuevo escaneo (habitualmente comprobando el efecto del último número). Hay una serie de tácticas de eliminación. Una de las más comunes es el "borrado del candidato no coincidente". Las celdas con idéntica configuración de números candidatos se dice que coinciden si la cantidad de números candidatos en cada una es igual al número de celdas que los contienen. Por ejemplo, se dice que celdas coinciden con una particular fila, columna o región si dos celdas contienen el mismo par de números candidatos (p, q) y no otros, o si tres celdas contienen el mismo triplete de números candidatos (p, q, r) y no otros. Estas son, esencialmente, contingencias coincidentes. Estos números (p, q, r) que aparecen como candidatos en cualquier lugar en la misma fila, columna o región en celdas no coincidentes, pueden ser borrados.
"y-si": se selecciona una celda con sólo dos números candidatos y se realiza una conjetura. Las etapas de arriba se repiten a menos que se encuentre una duplicación, en cuyo caso el candidato alternativo es la solución. En términos lógicos este método se conoce como reducción al absurdo. "Nishio" es una forma limitada de esta aproximación: para cada candidato para una celda, la cuestión que se plantea: ¿entrará un número particular de una configuración en otro emplazamiento? Si la respuesta es sí, entonces ese candidato puede ser eliminado.
