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. Aunque se podrÃan usar colores, letras, figuras... Lo que importa es que sean nueve elementos diferenciados. El motivo de usar números es que se memorizan mejor. No se debe repetir ninguna cifra en una misma fila, columna o subcuadrÃcula. Un sudoku está bien planteado si la solución es única. La resolución del problema requiere paciencia y ciertas dotes lógicas.
En realidad, no es estrictamente necesario utilizar números, sino que se pueden utilizar letras, formas o colores sin alterar las reglas, pero se utilizan números por comodidad. La cuadrÃcula más común es de 9x9 con regiones de 3×3, pero también se utilizan otros tamaños. Además, las regiones no tienen por qué ser cuadradas, aunque generalmente lo son.
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 región.
Numerosos periódicos han empezado a publicar el sudoku desde el 2005 en su sección de pasatiempos.
Tabla de contenidos |
Este rompecabezas numérico puede haberse originado en Nueva York en 1979. Entonces, la empresa Dell Magazines publicó este juego, ideado por Howard Garns, bajo el nombre de Number Place (el lugar de los números).
Es muy probable que el Sudoku se crease a partir de los trabajos de Leonhard Euler, famoso matemático suizo del siglo XVIII. Dicho matemático no creó el juego en sÃ, sino que utilizó el sistema llamado del cuadrado latino para realizar cálculos de probabilidades.
Posteriormente, la editorial Nikoli lo exportó a Japón, publicándolo en el periódico Monthly Nikolist en abril de 1984 bajo el tÃtulo "SÅ«ji wa dokushin ni kagiru" , que se puede traducir como "los números deben estar solos" (significa literalmente "célibe, soltero"). Fue Kaji Maki , presidente de Nikoli, quien le puso el nombre. Posteriormente, el nombre se abrevió a SÅ«doku (sÅ« = número, doku = solo); ya que es práctica común en japonés tomar el primer kanji de palabras compuestas para abreviarlas.
En 1986, Nikoli introdujo dos innovaciones que garantizarÃan la popularidad del rompecabezas: el número de cifras que venÃan dadas estarÃa restringida a un máximo de 30 y serÃa "simétrico" (es decir, las celdas con cifras dadas estarÃan dispuestas de forma rotacionalmente simétrica). Esto no siempre se cumple en los sudokus actuales. En 1997 Wayne Gould preparó algunos sudokus para el diario The Times, que los publicó bastante más tarde, en diciembre de 2004. Tres dÃas después, The Daily Mail publicó sus sudokus con el nombre codenumber. En 2005 muchos otros periódicos de todo el mundo empezaron a incluir sudokus a diario en sus páginas.
En el año 2005, la ICPC (International Collegiate Programming Contest) incluyó entre sus 9 problemas el Sudoku.
En el año 2005 también ve a la luz el primer libro sobre Sudokus que publica un español, "Los mejores Sudokus", con 200 SuDokus agrupados en 4 niveles de dificultad, con una extensa descripción de la historia de este pasatiempo asà como de sus reglas y un ejemplo paso a paso para su resolución. A este primero le siguieron 3 volúmenes más, asà como un libro sobre Kakuros, otro sobre Cuadrados mágicos, y uno más sobre el Cuboku.
En 1997, el juez jubilado de Hong-Kong Wayne Gould, de 59 años de edad, un neozelandés, vio un rompecabezas parcialmente completado en una librerÃa japonesa. Durante unos 6 años desarrolló un programa de ordenador para producir rompecabezas rápidamente. Sabiendo que los periódicos del Reino Unido tienen una larga tradición en cuanto a la publicación de crucigramas y otros rompecabezas, promovió el Sudoku en The Times en Gran Bretaña, publicándolo el 12 de noviembre de 2004 (llamándolo Su Doku). Los rompecabezas de Pappocom, empresa de software de Gould, se han impreso diariamente en el Times desde entonces.
Tres dÃas más tarde, The Daily Mail comenzó a publicar el rompecabezas bajo el nombre de "Codenumber". The Daily Telegraph introdujo su primer Sudoku de Michael Mepham el 19 de enero de 2005 y otros periódicos del Telegraph Group lo incluyeron rápidamente.
Nationwide News Pty Ltd comenzó a publicar el rompecabezas en The Daily Telegraph de Sydney el 20 de mayo de 2005; se imprimieron cinco rompecabezas con soluciones ese dÃa. La gran popularidad alcanzada por el Sudoku en los periódicos británicos e internacionalmente ha hecho que lo apodaran en los medios de comunicación mundiales en 2005 el "rompecabezas con un crecimiento más rápido en el mundo".
La escritora Carol Vorderman, en su libro Carol Vorderman's How To Do Sudoku explica por qué ella y muchas otras personas disfrutan resolviendo Sudokus.
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 sólo una vez. Además, cada número de la solución aparece sólo una vez en cada una de las tres "direcciones", de ahà el "los números deben estar solos" que evoca el nombre del juego.
La estrategia para resolver este rompecabezas se puede considerar como la combinación de tres procesos: escaneo, marcado y análisis.
El escaneo se realiza desde el principio y periódicamente, durante toda la resolución. El escaneo puede tener que 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.
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.
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 celdas. La desventaja es que los puzles 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 puzzle 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 puzle 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.
Hay dos aproximaciones principales - eliminación y "y-si".
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 seas bien organizado. El quid de la cuestión es encontrar una técnica que minimice el recuento, el marcado y el borrado.
Para los programadores es relativamente sencillo construir una búsqueda por el método de backtracking o "vuelta atrás". Ésta asignarÃa, tÃpicamente, un valor (supongamos que 1, o el más cercano a 1 disponible) a la primera celda disponible (supongamos que la superior izquierda) y entonces continuar asignando el siguiente valor disponible (supongamos que 2) a la siguiente celda disponible. Esto continuarÃa hasta que se descubriera una duplicación, en cuyo caso, el siguiente valor alternativo se colocarÃa en el primer campo alterado. En el caso de que ningún valor cumpliera la restricción se retrocederÃa hasta la casilla anterior y se probarÃan los siguientes números.
Aunque lejos de la eficiencia computacional, este método encontrará la solución si se permite el suficiente tiempo de computación. Un programa más eficiente podrÃa dejar una huella de valores potenciales para las celdas, eliminando valores imposibles hasta que sólo un valor quedase para una celda determinada. Entonces se rellenarÃa esa celda y se usarÃa esa información para más eliminaciones y asÃ, sucesivamente hasta el final. Esto emularÃa más exactamente lo que un resolutor humano harÃa sin el método de ensayo y error.
Codificar la búsqueda para imposibilidades basadas en contingencias e incluso múltiples contingencias (como serÃa requerido para los Sudoku más difÃciles) es bastante complejo de construir a mano. De cualquier modo, tales complicaciones son innecesarias si todo lo que el programador desea hacer es encontrar una solución eficientemente. Una forma más eficiente de construir soluciones involucra herramientas de programación más avanzadas.
Algunos programas asà construidos, que emulan la resolución humana, permiten estimar la dificultad que tendrá un humano para encontrar la solución.
A menudo, los sudokus publicados se clasifican según su dificultad. Aunque resulta sorprendente, la cantidad de números dados apenas afecta a la dificultad del sudoku, e incluso puede no afectar en absoluto. Un sudoku con un mÃnimo de números dados puede ser muy fácil de resolver, y uno con más números de la media puede ser extremadamente complicado de resolver. Está basado en la relevancia y la posición de los números más que en la cantidad de éstos. Se ha demostrado que el problema de resolución de Sudoku pertenece a NP Complexity_classes_P_and_NP (problemas cuya complejidad no es polinómica), por lo tanto (en teorÃa) no se puede construir un algoritmo que los resuelva en un tiempo polinómico .
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 online también ofrecen varios niveles de dificultad.
Es posible establecer sudokus con más de una solución y también realizar tableros iniciales de sudoku sin solución, pero no se consideran rompecabezas Sudoku apropiados; como la mayor parte de los rompecabezas lógicos, se espera una solución única.
La construcción de un rompecabeza Sudoku puede ser realizada a mano eficientemente predeterminando las posiciones de los números dados y asignándoles valores para realizar un proceso deductivo.
Se piensa que los Sudokus Number Place de Dell están generados por computador. Normalmente tienen más de 30 números dados dispersos aparentemente de forma aleatoria, algunos de los cuales pueden ser deducidos a partir de otros números dados. También tienen créditos sin autorÃa (es decir, el nombre del constructor no se imprime junto a ningún puzzle). Wei-Hwa Huang asegura que Dell le encargó escribir un programa generador Number Place en invierno del año 2000; antes de ello, le dijeron que los Sudokus eran realizados a mano. El generador fue escrito con Visual C++, y aunque tenÃa opciones para generar más rompecabezas de estilo japonés, con restricciones simétricas y menos números, Dell optó por no usar esas funciones, al menos no hasta su reciente publicación de las revistas compuestas Ãntegramente por Sudokus.
Los Sudoku Nikoli se construyen a mano, y el nombre del autor aparece en los créditos junto a cada rompecabeza; 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 números dados simétricos. The Guardian licencia y publica rompecabezas Sudoku construidos con Nikoli, aunque no incluye créditos de autorÃa. The Guardian declaró que ya que eran realizados a mano, sus rompecabezas contendrÃan "ocurrencias imperceptibles" que serÃan poco 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 forma 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.
Aunque los Sudokus de 9×9 con regiones de 3×3 son, por mucho, los más comunes, abundan numerosas variaciones. Por ejemplo, hay Sudokus de tablas de 4×4 con regiones de 2×2; se han publicado bajo el nombre de Logi-5 tablas de 5×5 con regiones pentaminó; el World Puzzle Championship ha realizado previamente una tabla de 6×6 con regiones de 2×3 y una tabla de 7×7 con seis regiones heptomino y una región disjunta; Daily SuDoku ofrece Sudokus de 4×4, 6×6, y 9×9 sencillos cada dÃa bajo el nombre de Daily SuDoku for Kids [1]. Incluso el Sudoku de 9×9 no es siempre estándar, y Ebb publica regularmente algunos de ellos con regiones nonomino; los U.S. Puzzle Championship de 2005 tenÃan un Sudoku con regiones de paralelogramos dispuestas alrededor del borde externo del rompecabezas, como si la tabla fuese toro (matemáticas)|toroidal. También se pueden realizar Sudokus más grandes, como el Monster SuDoku de 12×12 de Daily SuDoku [2], los Number Place Challenger de 16×16 que publica Dell regularmente y el desafiante Sudoku el Gigante Behemoth|behemoths de Nikoli de 25×25.
Otra variante común consiste en establecer restricciones adicionales para forzar la posición de los números más allá de los habituales requisitos en cuanto a fila, columna y región. A menudo, las restricciones toman la forma de una "dimensión" extra; la más común es que se cumpla el requisito de que los números de las diagonales principales también sean únicos. Los mencionados Sudokus Number Place Challenger forman parte de esta variante, asà como lo son los Sudoku X del Daily Mail, que utiliza rejillas de 6×6. El Daily Mail también publica el Super Sudoku X en su revista Weekend: una rejilla de 8×8 en la que las filas, columnas, diagonales principales, bloques de 2×4 y bloques de 4×2 contienen cada número una sola vez. Otra variante consiste en emplear dÃgitos con la misma posición relativa dentro de sus respectivas regiones; dichos rompecabezas se imprimen a menudo en color, de forma que cada grupo disjunto comparte un color para mayor claridad.
Otras clases de restricciones extra pueden ser matemáticas, como requerir que los números en segmentos delineados de la rejilla tengan sumas especÃficas o productos (un ejemplo de lo anterior serÃa el Killer Su Doku en The Times). También son frecuentes los rompecabezas construidos a partir de múltiples Sudokus. Las rejillas de 9×9 que se superponen en las regiones de las esquinas en forma de un quincuncio son concidas en Japón como Sudoku Gattai 5 (mezcla de cinco), pero también reciben el nombre de Super Sudoku. En The Times y The Sydney Morning Herald a este tipo de Sudokus les llaman Samurai SuDoku (Sudoku Samurái en español). Sudokus con 20 ó más regiones que se superponen son comunes en algunas publicaciones japonesas. A menudo, no se ofrecen números dados en las regiones solapadas. También se publican rejillas secuenciales, en contraposición a las solapadas, con valores en lugares especÃficos en las rejillas que necesitan ser transferidos a otras.
También han emergido variaciones alfabéticas, que utilizan letras en lugar de números. Por supuesto, no hay diferencia funcional en el rompecabezas salvo que las letras deletreen algo. Las variantes recientes inciden en esto, a menudo haciendo que aparezca una palabra en una de las diagonales principales una vez solucionado el Sudoku; la determinación de la palabra se puede ver como una ayuda por adelantado para llegar a la solución. El Code Doku [3] ideado por Steve Schaefer tiene una oración entera encajada en el rompecabezas; el Super Wordoku [4] de Top Notch representa dos palabras de 9 letras, una en cada diagonal. Es discutible si éstos son verdaderos Sudokus: aunque presumiblemente tienen una sola solución válida lingüÃsticamente, no tienen por qué tener que ser solucionados basándose únicamente en la lógica, necesitando que el que lo resuelva determine cuáles son las palabras incrustadas. Top Notch alega que ésta es una caracterÃstica que se diseñó para derrotar a los programas de resolución de Sudokus.
A continuación, algunas de las variaciones únicas más importantes:
