thumb|300px|Ejemplo de sudoku thumb|300px|Sudoku resuelto Sudoku (en japonés: 数独, sūdoku) es un juego matemático que se inventó a finales de la década de 1970, adquirió popularidad en Japón en la década de 1980, y se dio a conocer en el ámbito internacional en 2005, cuando numerosos periódicos empezaron a publicarlo en su sección de pasatiempos.
El objetivo del sudoku 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. La forma inicial del juego es que sean nueve elementos diferenciados, que no se deben repetir en una misma fila, columna o subcuadrícula. Un sudoku bien planteado solo puede tener una solución, y ha de tener al menos 17 pistas iniciales.«Las claves matemáticas para resolver un sudoku», en Abc, 10/01/2012. Un sudoku no se puede resolver si no hay un mínimo de 17 cifras-pista en su inicio, ya que con menos «no existe una solución única». La mayor parte de las veces cuenta con unas 25 cifras-pista. A medida que bajan las pistas, más difícil es su resolución. La solución de un sudoku siempre es un cuadrado latino, aunque el recíproco en general no es cierto ya que el sudoku establece la restricción añadida de que no se puede repetir un mismo número en una subcuadrícula.
Historia
En el el famoso matemático suizo Leonhard Euler creó un sistema de probabilidades para representar una serie de números sin repetir. Debido a esto, Euler se considera el inventor de este juego.
Ya en 1970 la editorial Math Puzzles and Logic Problems publicaba una sección llamada Number place por lo que este enigma matemático se convertiría en pasatiempos, aunque años más tarde se perdió en el olvido.
En 1984 el periódico japonés Monthly Nikolist publicó una sección de pasatiempos llamada Sūji wa dokushin ni kagiru () «los números deben ser únicos» (literalmente dokushin () = «célibe, soltero»). Fue Maki Kaji, presidente de Nikoli, quien le puso el nombre. El nombre se abrevió a Sūdoku (sū = número, doku = solo).
Se comenzó a conocer internacionalmente en 2005, cuando varios periódicos empezaron a publicarlo como pasatiempo.
Reglas y terminología El sudoku se presenta habitualmente como una tabla de 9 × 9, compuesta por subtablas de 3 × 3 denominadas «regiones» (también se le llaman «cajas» o «bloques»).
Algunas celdas ya contienen números, conocidos como «números dados» (o a veces «pistas»). El objetivo es rellenar las celdas vacías, con un número en cada una de ellas, de tal forma que cada columna, fila y región contenga los números 1–9 solo una vez.
Además, cada número de la solución aparece solo una vez en cada una de las tres «direcciones», de ahí el «los números deben estar solos» que evoca el nombre del juego.
Métodos de resolución
Archivo:Soduku_ejemplo_de_trazado.png
La casilla marcada en verde de la región 3 × 3 de la esquina superior izquierda debe contener un 7.
La estrategia para resolver este rompecabezas se puede considerar como la combinación de tres procesos: rastreo, marcado y análisis.
thumb|150px|Patrón de marcado de puntos (segunda notación)
Rastreo
En el ejemplo anterior, rastreando a lo largo y ancho los sietes localizados en cualquier lugar de la rejilla, el jugador puede eliminar todas las celdas vacías de la esquina superior izquierda que no pueden contener un 7. Esto deja sólo una celda posible (marcada en verde).
Marcado
El rastreo 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 celdas. La desventaja es que los rompecabezas originales se publican en periódicos que habitualmente no dejan demasiado espacio para acomodar más que unos pocos dígitos. Si se usa esta notación, los resolutores crean, a menudo, una copia más grande del rompecabezas y emplean un lápiz afilado.
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. Esta notación tiene como ventaja que puede usarse en el rompecabezas original. Se requiere destreza para el emplazamiento de los puntos, porque la existencia de puntos desplazados o marcas inadvertidas lleva, inevitablemente, a confusión y no son fáciles de borrar sin añadir más confusión.
Análisis Hay dos aproximaciones principales: En eliminación, el progreso se realiza mediante la sucesiva eliminación de números candidatos para una o más celdas, hasta dejar solo una elección. Después de lograr cada respuesta, debe realizarse un nuevo rastreo (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. Esta aproximación puede ser desaprobada por puristas lógicos por demasiado ensayo y error pero puede llegar a soluciones claras y rápidamente.
Idealmente, se necesita encontrar una combinación de técnicas que eviten alguno de los inconvenientes de los elementos de arriba. El recuento de regiones, filas y columnas puede resultar aburrido. Escribir números candidatos en celdas vacías puede consumir demasiado tiempo. La aproximación «y-si» puede ser confusa a menos que se sea bien organizado. La intención de la cuestión es encontrar una técnica que minimice el recuento y el marcado.
En inglés se publicó un análisis sustematico de la lógica y de las técnicas de resolución: «Pattern-Based Constraint Satisfaction and Logic Puzzles».
Métodos básicos analítico-sistemáticos
Resolver sudokus requiere un enfoque sistemático, y hacen falta análisis y pensamiento lógico. Los sudokus fáciles a menudo pueden resolverse mentalmente mediante el pensamiento lógico. Para problemas más desafiantes, puede ser necesario tomar notas para registrar diferentes soluciones posibles para cada campo (candidato).
En lo sucesivo, se entiende por solución analítico-sistemática de un sudoku la combinación de métodos que, tras un examen relativamente corto y claro, conducen a un resultado claro para una posición previamente no establecida. Ejemplos de tales métodos son la criba (escaneo), recuento y los nuevos procedimientos de exclusión de candidatos. Si todas las posiciones pueden decidirse de este modo, entonces -en contraste con la comprobación (falsificación de una hipótesis)- está garantizado salir del paso con una sola hoja.
Contar en unidades «Método de los desnudos»: Primero se selecciona un campo. Para este campo, se excluyen todos los dígitos que ya están en la misma unidad (fila, columna o bloque). Si sólo queda un dígito, es la solución para este campo. (Sólo queda un dígito para la posición considerada.) Es aconsejable empezar por las columnas, filas o bloques con menos campos vacíos, ya que lo más probable es que aquí se puedan excluir todos los dígitos menos uno. «Método de los ocultos»: Con este método, se observa una unidad (fila, columna o bloque) y un dígito que aún no se ha introducido en esta unidad. Como cada dígito aparece exactamente una vez en una unidad, debe introducirse en uno de los campos libres. Si sólo hay un campo libre en esta unidad en la que el dígito se puede introducir sin que se produzca más de una vez en otra unidad, se introduce en este campo.
Visualización de dígitos Primero se selecciona un dígito al azar y luego se miran todos los campos ya rellenados con este dígito uno tras otro (valores por defecto y soluciones). Los demás campos de la unidad correspondiente (sea fila, columna o bloque) se excluyen por regla. Si se excluyen todos los campos de una unidad excepto uno, el dígito candidato del campo restante se convierte en la solución (según el método de los ocultos mencionado anteriormente). A continuación, se continúa del mismo modo con el siguiente dígito.
Si introduce (provisionalmente) los dígitos que aún no aparecen en las unidades respectivas (fila, columna o bloque) en cada campo, podrá reconocer los ocultos por el hecho de que sólo quede un dígito en un campo. En el caso de las ocultas, el dígito en cuestión aparece exactamente una vez en una unidad.
Otros métodos de exclusión (eliminación) Se trata de métodos que permiten reducir aún más el conjunto candidato de campos individuales. Conviene empezar por los que sólo se aplican a una unidad. En principio, el orden en que se aplican puede invertirse.
Método Twin (Doble gemelo): El método Twin directo: Si en celdas de una unidad (fila, columna o bloque) solo quedan los mismos candidatos, es decir, si los conjuntos de candidatos de estas celdas no contienen más cifras, entonces en cada una de las celdas debe haber una de estas cifras (salvo en , donde aún no se sabe qué cifra corresponde a qué celda). Por lo tanto, estas cifras no pueden aparecer en ninguna otra celda de la unidad afectada. Si para el doble gemelo se encuentra, por ejemplo, en una fila, se deben eliminar los candidatos en las celdas restantes de esa fila. De manera análoga, esto se aplica a la columna o bloque.En el doble gemelo / «Doble twin» se pueden incluso eliminar dos unidades al mismo tiempo: por ejemplo, fila y bloque o columna y bloque, como se muestra en el ejemplo «Imagen: Patrón lógico A» – Ejemplo verde. Aquí, por ejemplo, ni el 5 ni el 9 pueden aparecer en la zona de fondo verde. El método Twin indirecto (oculto): Nuevamente se considera una unidad y se buscan cifras que solo aparecen en exactamente celdas de esa unidad, es decir, ninguna de estas cifras aparece en otro conjunto de candidatos dentro de esta unidad considerada. Entonces, en cada una de las celdas debe haber una de estas cifras, y se pueden eliminar todos los demás candidatos de estas celdas. Un ejemplo para es en la imagen «con todos los candidatos restantes», en la fila 8, la celda g8 con las cifras 3 y 6, una configuración que elimina el 3 de esa celda; o para , la columna f con las celdas f1 y f9 y las cifras 6 y 8. A través de esta eliminación, el Twin indirecto se convierte en un Twin directo y se hacen posibles las eliminaciones de candidatos descritas allí.
Método de los Triples desnudos (Triple): Representa una analogía al método directo Twin. Si en celdas de una unidad solo aparecen cifras como candidatos (esto puede ocurrir incluso en , hasta el par de cifras por celda; una configuración que también se llama «Swordfish» = pez espada), estas cifras deben eliminarse de otras celdas de la misma unidad (fila, columna o bloque). Un ejemplo son en la columna f las celdas f5 y f7, lo que elimina los dos candidatos 3 y 7 en todas las demás celdas de esa columna. De esta manera, en cada paso de eliminación por unidad se forman listas de candidatos disjuntas; en el ejemplo, las cifras 1 y 4 en las celdas f4 y f6. En el Doble Triple las celdas consideradas no están solo en una fila o columna, sino también en el mismo bloque. Entonces, estos candidatos no solo pueden eliminarse en las celdas restantes de la misma fila o columna, sino también en el bloque (Ejemplo: Candidatos 3, 5, 7 en las celdas d7–f7 en la fila 7 y en el bloque d7–f9 en la imagen «con todos los candidatos restantes»).