Sudoku

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.​

Ejemplo de sudoku

Sudoku resuelto

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.​ ​ 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 siglo XVIII 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 normalmente 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

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.

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.

Una sistemática análisis de la lógica y de las técnicas de resolución fue publicada in Inglés: "Pattern-Based Constraint Satisfaction and Logic Puzzles".​

Métodos básicos analítico-sistemáticos

1. Método «Cribado»: Tomar una cifra frecuente, por ejemplo «5». No se permiten más «5» en las líneas rojas. La única posición libre en el bloque superior derecho para un «5» es, por tanto, el campo marcado en verde. 2º  método «counting through»: Para el campo marcado en azul en el centro, se eliminan todos los dígitos ya especificados en la fila y columna (todos enmarcados en azul), no hay más en el bloque. Sólo queda el candidato «5» para este campo.

Resolver Sudokus requiere un enfoque sistemático, análisis y pensamiento lógico son necesarios. 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 Criba (escaneo), recuento, 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 $n\geq 1$ celdas de una unidad (fila, columna o bloque) solo quedan los mismos $n$ candidatos, es decir, si los conjuntos de candidatos de estas celdas no contienen más cifras, entonces en cada una de las $n$ celdas debe haber una de estas $n$ cifras (salvo en $n=1$, 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 $n>1$ el doble gemelo se encuentra, por ejemplo, en una fila, se deben eliminar los $n$ 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 $n\geq 1$ cifras que solo aparecen en exactamente $n$ 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 $n$ celdas debe haber una de estas $n$ cifras, y se pueden eliminar todos los demás candidatos de estas $n$ celdas. Un ejemplo para $n=1$ 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 $n=2$, 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 $n\geq 2$ celdas de una unidad solo aparecen $n$ cifras como candidatos (esto puede ocurrir incluso en $n\geq 3$, hasta el par de cifras por celda; una configuración que también se llama "Swordfish" = pez espada), estas $n$ 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 $n\leq 3$ 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").
• El Swordfish (= pez espada, ver también arriba): Esta estructura es muy parecida al método directo Twin, pero se trata de celdas emparejadas no solo en 2, sino en 3 filas/columnas, donde exactamente un extremo en la columna/fila coincide emparejadamente con un extremo de otro par en la columna/fila, de modo que los extremos del todo forman una figura cerrada en forma de anillo. Incluso en este caso, la cifra de candidato en las 3 columnas/filas afectadas está excluida de las 7 celdas restantes de cada columna/fila.
• El método X-Wing: La condición previa para esto es una disposición emparejada de un solo candidato en dos unidades:
  • X-Wing simétrico: En dos filas (o columnas) una cifra de candidato aparece exclusivamente en dos columnas (o filas) idénticas. Estas 4 celdas deben estar en al menos 2 bloques diferentes, pero también pueden estar en 4 bloques. Estas cuatro celdas posibles de intersección representan las esquinas de un rectángulo imaginario o forman un patrón simétrico en forma de X. Los verdaderos puntos de solución deben estar obligatoriamente en los extremos de una de las dos diagonales posibles. En consecuencia, este candidato debe eliminarse en los 2*7 campos restantes de las dos columnas (o filas) y en los campos restantes de los bloques comunes.
  • X-Wing asimétrico (Tipo A): En dos filas (o columnas) una cifra de candidato aparece solo dos veces. Cada una de estas filas (columnas) se encuentra en la misma columna (fila), mientras que las dos restantes están en un bloque común. Aquí se forma una figura X asimétrica. Los extremos de las posibles dos diagonales forman los puntos de un trapecio. Esto provoca una exclusión de candidatos en los 7 campos restantes de una columna (o fila) común o de los bloques comunes (ver imagen: Patrón lógico B ejemplo rojo y amarillo).
  • X-Wing asimétrico (Tipo B): En dos filas (o columnas) una cifra de candidato aparece solo dos veces. Sin embargo, no hay una posición emparejada en una columna (fila), sino que dos de ellas se encuentran en los mismos bloques. También se forma una figura X en este caso. Los extremos de las posibles dos diagonales forman los puntos de un trapecio. Esto provoca una exclusión de candidatos en los 7 campos restantes de los bloques comunes.
  • X-Wing asimétrico (Tipo C): En dos bloques, una cifra de candidato aparece dos veces. Cada candidato se encuentra en la misma fila (o columna). En este caso, las posibles intersecciones también forman un trapecio. Esto provoca una exclusión de candidatos en los dos 7 campos restantes de las filas (columnas) comunes (ver imagen: Patrón lógico B ejemplo rojo y amarillo).
• Interacción de bloques: Si un candidato numérico en dos bloques dispuestos horizontal (o vertical)mente está excluido en una (!) fila (o columna) común entre los dos bloques (sin haber sido ya ingresado como solución en los tres bloques considerados), entonces debe aparecer como solución en este bloque restante en esta fila, y de este modo está excluido en las dos filas restantes (o columnas) de este bloque (comparar imagen: Patrón lógico C ejemplo rosa; aunque allí se consideraron pares, esto también se aplica a cada candidato individual).
• Comprobación de bloque-fila: Si en un bloque no se puede asignar de manera inequívoca una cifra candidata a una celda, pero todas las celdas del bloque donde esta cifra todavía es posible se encuentran en una sola fila (es decir, fila o columna), entonces la cifra candidata elimina todas sus demás apariciones en la fila respectiva fuera del bloque. Un ejemplo de "Comprobación de bloque a fila" es la situación en el bloque d1–f3: allí, la cifra candidata 6 solo aparece en la fila 1 de este bloque. Por lo tanto, debe ser colocada en esta fila para este bloque, por ejemplo, en la celda d1 o la celda f1, y no puede aparecer fuera de este bloque en la fila 1, por ejemplo, en las celdas a1–c1 o g1–i1. De manera similar, existe una "Comprobación de bloque a columna" para la cifra candidata 4 en las celdas f4 y f6 del bloque d4-f6, lo que elimina el 4 como candidato en las celdas f1 y f3.

Niveles de dificultad

Los programas informáticos que resuelven sudokus pueden estimar la dificultad que tiene un humano para encontrar la solución, basándose en la complejidad de las técnicas de resolución necesarias. Esta estimación permite a los editores adaptar sus sudokus para personas con diferente experiencia resolutoria. Algunas versiones "en línea" (online) también ofrecen varios niveles de dificultad.

Construcción

Un sudoku debe tener una única solución para que se considere bien planteado; es decir, a partir de las pistas iniciales sólo puede haber una forma válida de completar las casillas restantes. Para que un sudoku posea una única solución, es necesario que el número de pistas iniciales sea al menos 17; esto se demostró en 2012.​

La construcción de un sudoku puede ser realizada a mano eficientemente predeterminando las posiciones de los números dados y asignándoles valores para realizar un proceso deductivo.

Los sudokus Nikoli se construyen a mano, y el nombre del autor aparece en los créditos junto a cada rompecabezas; los números dados siempre se encuentran en forma de un patrón simétrico. Los rompecabezas Number Place Challenger de Dell (véase Variantes más abajo) también citan los créditos del autor. Los rompecabezas sudoku que aparecen en la mayoría de los periódicos del Reino Unido aparentemente son generados por ordenador, pero emplean probables en sudokus generados por ordenador. El desafío para los programadores de sudokus es enseñar a un programa cómo construir rompecabezas inteligentes, de manera que no se puedan distinguir de aquellos realizados por humanos; Wayne Gould necesitó retocar su popular programa durante seis años para creer que había alcanzado ese nivel.

Variantes

Aunque lo más común es que la tabla tenga un tamaño de 9x9 con regiones de 3x3, hay numerosas variantes. Los juegos de iniciación pueden ser tablas de 4x4 con regiones de 2x2; bajo el nombre de Logi-5, se han publicado tablas de 5x5 con pentominós como regiones; el World Puzzle Championship ha publicado una tabla de 6x6 con regiones de 2x3 y una tabla de 7x7 formada por 6 regiones compuestas por heptominós y una región separada. También se pueden encontrar tablas de mayor tamaño. El diario The Times propone el Dodeka Sudoku, una tabla de 12x12 con 12 regiones de 4x3. Dell Magazines publica con frecuencia juegos de 16x16 (la variante de 16x16 utiliza normalmente los símbolos del 1 a la G, en lugar de los símbolos del 0 a la F usados en hexadecimal). El editor de puzles Nikoli propone el Sudoku Gigante de 25x25.

Un Sudoku hecho de nonominós (poliominós de 9 celdas), como los del The Sunday Telegraph

La solución del puzle anterior son los números en rojo

Otra variante frecuente es añadir límites en la colocación de los números aparte de mantener los requisitos normales sobre filas, columnas y regiones. Con frecuencia, los límites toman la forma de una “dimensión” extra; lo más común es obligar a que los números de la diagonal principal de la tabla sean únicos. Los ya mencionados juegos Number Place Challenger incluyen esta variante. También forman parte de esta variante los juegos del Daily Mail que utilizan tablas de 6x6.

El periódico americano USA Today publica otra variante denominada “Mini Sudoku”, consistente en una tabla de 6x6 con regiones de 3x2. El objetivo es el mismo que en el Sudoku original, pero en esta variante solo se utilizan números del 1 al 6.

Otra variante es la combinación del Sudoku y el Kakuro en una tabla de 9x9, denominada Sudoku de Sumas Cruzadas, en la que las pistas se dan a través de sumas cruzadas. También es posible que las pistas se den mediante criptoaritmos en los que cada letra representa un único dígito del 0 al 9. Un ejemplo es: NUMBER+NUMBER=KAKURO cuya única solución es 186925+186925=373850. Otro ejemplo es SUDOKU=IS*FUNNY cuya solución es 426972=34*12558.

Un Sudoku Killer.

Solución del puzle de arriba.

El Addoku combina elementos de Sudoku y Kakuro – normalmente no se dan números iniciales, sino que la tabla de 9x9 se divide en regiones, cada una de las cuales contiene la suma de todos los números de la región teniendo además en cuenta que no hay números repetidos en la misma región. A la hora de completar la tabla se mantienen además las reglas del Sudoku original.

Una de las variantes más populares es el Hypersudoku. Se publica en periódicos y revistas de todo el mundo y también es conocido por “Sudoku NRC Handelsblad”, “Windoku”, “Hiper-Sudoku” y “Sudoku 4 cuadros”. La base es idéntica a la del Sudoku original, pero incluye áreas interiores adicionales en las que deben aparecer números del 1 al 9. El algoritmo que lo resuelve es ligeramente diferente del Sudoku normal por la influencia de los cuadros solapados. Este solapamiento da al jugador más información que permite reducir las posibilidades de los restantes cuadros. La forma de jugar es similar a la del Sudoku pero es necesario prestar más atención a las cuadros y a las zonas solapadas que a las filas y columnas.

Un Sudoku de letras

La solución del anterior está en rojo

También son comunes los juegos construidos a partir de múltiples tablas de Sudoku. En Japón es conocido el Sudoku Gattai 5 (mezcla de 5) compuesto por 5 tablas de 9x9 con solapamiento en las regiones de las esquinas con forma de quincuncio. En diarios como The Times o The Sydney Morning Herald, esta variante se conoce como Sudoku Samurai. Otros como el Baltimore Sun y el Toronto Star publican esta variante en su edición dominical con el nombre High Five. Con frecuencia, no se proporcionan pistas en las regiones solapadas. También se publican variantes con tablas secuenciales, en lugar de solapadas, en las que los valores de determinadas posiciones se transfieren de una tabla a otra.

El Sudoku Social es una versión digital multijugador de Sudoku que permite a 2 jugadores jugar al mismo tiempo sobre el mismo tablero. Esta variante fue creada por Crosswords Ltd. en 2010 y lanzada como aplicación para la plataforma iOS de Apple a través de su Game Center. El Sudoku Social[2] concede puntos a cada jugador a medida que van colocando los números correctamente, bloqueando el cuadro seleccionado al otro jugador. Las jugadas incorrectas hacen que el jugador no tenga acceso al tablero durante 10 segundos, además de provocar la pérdida de puntos.

También han surgido variantes alfabéticas, llamadas a veces Sudokus de letras (Wordokus): no existe diferencia funcional a menos que las letras formen palabras. Algunas variantes, como la de TV Guide, incluyen una vez resuelto el juego una palabra en la diagonal principal, en una fila o en una columna; determinar la palabra por adelantado puede ser una ayuda para la resolución del juego. Un Wordoku puede contener otras palabras además de la palabra principal. Como en el ejemplo de la derecha, las palabras “Kari”, “Park” y “Per” podrían formar parte de la solución. Esto debería evitarse sustituyendo, por ejemplo, el carácter “R” por el carácter “Q”. Por otro lado el Sudoku Ripeto permite repetir símbolos y el Custom Sudoku mostrar palabras en el tablero antes de la resolución.

Custom Sudoku con una palabra y letras repetidas

Otra variante sin diferencia funcional es el Quadratum Latinum con Numeración romana de Hebdomada Aenigmatum, la revista de crucigramas íntegramente en latín de Luca Desiata.​

Con una baraja estándar de 81 cartas del juego Set! puede jugarse al Sudoku. La versión tridimensional del Sudoku fue inventada por Dion Church y publicada en el Daily Mail Telegraph en mayo de 2005. También existe una versión del cubo de Rubik denominada el cuboku.

Un ejemplo de Sudoku Mayor que.

Hay otras muchas variantes. Algunas presentan diferentes formas en la disposición de los solapamientos de tablas de 9x9, tales como una mariposa, un molino o una flor.​ Otras versiones varían en la lógica de resolución del juego. Una de ellas es Sudoku Mayor que. En esta versión, cada región de 3x3 contiene 12 símbolos de mayor (>) o menor (<) en la línea común de dos números adyacentes.​ Otra variante de este tipo es Sudoku Sin pistas en el que se colocan nueve tablas de Sudoku de 9x9 en una matriz de 3x3. La celda central de cada región de 3x3 en cada una de las 9 tablas se deja en blanco, formando un décimo Sudoku sin ninguna celda completa; de ahí el nombre "sin pistas".​

Véase también

• Algoritmos para la resolución de sudokus
• Cuadrado mágico
• Hitori

Referencias

• Datos: Q44914
• Multimedia: Sudoku / Q44914