Sudoku ( / s uː ˈ d oʊ k uː , - ˈ d ɒ k -, s ə -/ ; japonés :数独, romanizado : sūdoku , lit. 'dígito único'; originalmente llamado Number Place ) [1] es un rompecabezas de colocación de números basado en la lógica [ 2] [3] combinatorio [4] . En el Sudoku clásico, el objetivo es llenar una cuadrícula de 9 × 9 con dígitos de modo que cada columna, cada fila y cada una de las nueve subcuadrículas de 3 × 3 que componen la cuadrícula (también llamadas "cajas", "bloques" o "regiones") contengan todos los dígitos del 1 al 9. El creador del rompecabezas proporciona una cuadrícula parcialmente completa, que para un rompecabezas bien planteado tiene una única solución.
Los periódicos franceses presentaron variaciones de los rompecabezas Sudoku en el siglo XIX, y el rompecabezas ha aparecido desde 1979 en libros de rompecabezas bajo el nombre de Number Place. [5] Sin embargo, el Sudoku moderno solo comenzó a ganar popularidad generalizada en 1986 cuando fue publicado por la compañía de rompecabezas japonesa Nikoli bajo el nombre Sudoku, que significa "número único". [6] Apareció por primera vez en un periódico estadounidense, y luego en The Times (Londres), en 2004, gracias a los esfuerzos de Wayne Gould , quien ideó un programa de computadora para producir rápidamente rompecabezas únicos.
Los acertijos numéricos aparecieron en los periódicos a finales del siglo XIX, cuando los solucionadores de acertijos franceses comenzaron a experimentar con la eliminación de números de los cuadrados mágicos . Le Siècle , un diario parisino, publicó un cuadrado mágico de 9×9 parcialmente completado con subcuadrados de 3×3 el 19 de noviembre de 1892. [7] No era un Sudoku porque contenía números de dos dígitos y requería aritmética en lugar de lógica para resolverlo, pero compartía características clave: cada fila, columna y subcuadrado sumaban el mismo número.
El 6 de julio de 1895, el rival de Le Siècle , La France , refinó el rompecabezas hasta convertirlo en casi un sudoku moderno y lo llamó carré magique diabolique ('cuadrado mágico diabólico'). Simplificó el rompecabezas del cuadrado mágico de 9 × 9 de modo que cada fila, columna y diagonales rotas contenían solo los números del 1 al 9, pero no marcaban los subcuadrados. Aunque no estaban marcados, cada subcuadrado de 3 × 3 comprendía de hecho los números del 1 al 9, y la restricción adicional sobre las diagonales rotas conducía a una sola solución. [8]
Estos rompecabezas semanales fueron una característica de los periódicos franceses como L'Écho de Paris durante aproximadamente una década, pero desaparecieron en la época de la Primera Guerra Mundial . [9]
El Sudoku moderno fue diseñado probablemente de forma anónima por Howard Garns , un arquitecto jubilado de 74 años y constructor de rompecabezas independiente de Connersville, Indiana , y publicado por primera vez en 1979 por Dell Magazines como Number Place (los primeros ejemplos conocidos de Sudoku moderno). [1] El nombre de Garns siempre estuvo presente en la lista de colaboradores en los números de Dell Pencil Puzzles and Word Games que incluían Number Place y siempre estuvo ausente en los números que no lo hacían. [10] Murió en 1989 antes de tener la oportunidad de ver su creación como un fenómeno mundial. [10] No está claro si Garns estaba familiarizado o no con alguno de los periódicos franceses mencionados anteriormente.
El rompecabezas fue introducido en Japón por Maki Kaji (鍜治 真起, Kaji Maki ) , presidente de la compañía de rompecabezas Nikoli, en el periódico Monthly Nikolist en abril de 1984 [10] como Sūji wa dokushin ni kagiru (数字は独身に限る) . que puede traducirse como "los dígitos deben ser únicos" o como "los dígitos están limitados a una sola aparición" (en japonés, dokushin significa "persona soltera"). Posteriormente, el nombre se abrevió a Sudoku (数独), tomando sólo el primer kanji de palabras compuestas para formar una versión más corta. [10] "Sudoku" es una marca registrada en Japón [11] y el rompecabezas generalmente se conoce como Number Place (ナンバープレース, Nanbāpurēsu ) o, de manera más informal, una abreviatura de las dos palabras, Num(ber) Pla(ce ) (ナンプレ, Nanpure ) . En 1986, Nikoli introdujo dos innovaciones: el número de datos se limitó a no más de 32 y los rompecabezas se volvieron "simétricos" (lo que significa que los datos se distribuyeron en celdas rotacionalmente simétricas ). Ahora se publica en publicaciones periódicas japonesas importantes, como Asahi Shimbun .
En 1997, el juez de Hong Kong Wayne Gould vio un rompecabezas parcialmente terminado en una librería japonesa. Durante seis años, desarrolló un programa informático para producir rompecabezas únicos rápidamente. [5] Sabiendo que los periódicos británicos tienen una larga historia de publicación de crucigramas y otros rompecabezas, promocionó Sudoku a The Times en Gran Bretaña, que lo lanzó el 12 de noviembre de 2004 (llamándolo Su Doku). La primera carta a The Times con respecto a Su Doku se publicó al día siguiente, el 13 de noviembre, de Ian Payn de Brentford , quejándose de que el rompecabezas le había hecho perder su parada en el metro . [12] Los rompecabezas de Sudoku se extendieron rápidamente a otros periódicos como una característica habitual. [5] [13]
El rápido ascenso del Sudoku en Gran Bretaña, desde una relativa oscuridad hasta ser un tema de portada en los periódicos nacionales, atrajo comentarios en los medios y parodias (como cuando la sección G2 de The Guardian se promocionó como el primer suplemento de periódico con una cuadrícula de Sudoku en cada página). [14] Reconociendo los diferentes atractivos psicológicos de los acertijos fáciles y difíciles, The Times presentó ambos, uno al lado del otro, el 20 de junio de 2005. A partir de julio de 2005, Channel 4 incluyó un juego de Sudoku diario en su servicio de teletexto . El 2 de agosto, la guía de programación de la BBC , Radio Times, presentó un Super Sudoku semanal con una cuadrícula de 16×16.
En Estados Unidos, el primer periódico que publicó un Sudoku de Wayne Gould fue The Conway Daily Sun (New Hampshire), en 2004. [15]
El primer programa de televisión en vivo de Sudoku, Sudoku Live , fue un concurso de rompecabezas que se transmitió por primera vez el 1 de julio de 2005 en Sky One . Fue presentado por Carol Vorderman . Nueve equipos de nueve jugadores (con una celebridad en cada equipo) que representaban regiones geográficas compitieron para resolver un rompecabezas. Cada jugador tenía un dispositivo portátil para ingresar números correspondientes a las respuestas de cuatro celdas. Phil Kollin de Winchelsea, Inglaterra , fue el ganador del gran premio de la serie, llevándose a casa más de £ 23,000 en una serie de juegos. La audiencia en casa participó en una competencia interactiva separada, que fue ganada por Hannah Withey de Cheshire .
Más tarde, en 2005, la BBC lanzó SUDO-Q , un programa de juegos que combinaba el sudoku con conocimientos generales. Sin embargo, solo utilizaba rompecabezas de 4x4 y 6x6. Se produjeron cuatro temporadas antes de que el programa terminara en 2007.
En 2006, un sitio web de sudoku publicó la canción de homenaje al sudoku del compositor Peter Levy, [16] pero rápidamente tuvo que retirar el archivo MP3 debido al tráfico excesivo. La embajada japonesa también nominó la canción para un premio, y Levy estuvo en conversaciones con Sony en Japón para lanzar la canción como sencillo. [17]
El software de Sudoku es muy popular en PC, sitios web y teléfonos móviles. Viene con muchas distribuciones de Linux . El software también se ha lanzado en consolas de videojuegos, como Nintendo DS , PlayStation Portable , Game Boy Advance , Xbox Live Arcade , el lector de libros electrónicos Nook , la tableta Kindle Fire, varios modelos de iPod y el iPhone . Muchos teléfonos Nokia también tenían Sudoku. De hecho, solo dos semanas después de que Apple Inc. debutara la App Store en línea dentro de su iTunes Store el 11 de julio de 2008, ya había casi 30 juegos de Sudoku diferentes, creados por varios desarrolladores de software , específicamente para el iPhone y el iPod Touch. Uno de los videojuegos más populares que presenta Sudoku es Brain Age: Train Your Brain in Minutes a Day!. Bien recibido por la crítica y comercialmente, generó elogios particulares por su implementación de Sudoku [18] [19] [20] y vendió más de 8 millones de copias en todo el mundo. [21] Debido a su popularidad, Nintendo creó un segundo juego Brain Age titulado Brain Age 2 , que tiene más de 100 nuevos Sudoku y otras actividades.
En junio de 2008, un juicio con jurado relacionado con drogas en Australia que había costado más de un millón de dólares australianos fue cancelado cuando se descubrió que cuatro o cinco de los doce jurados habían estado jugando al Sudoku en lugar de escuchar las pruebas. [22]
Aunque la cuadrícula de 9×9 con regiones de 3×3 es, con diferencia, la más común, existen muchas otras variantes. Algunos ejemplos de rompecabezas pueden ser cuadrículas de 4×4 con regiones de 2×2; cuadrículas de 5×5 con regiones de pentominó se han publicado bajo el nombre de Logi-5; el Campeonato Mundial de Rompecabezas ha presentado una cuadrícula de 6×6 con regiones de 2×3 y una cuadrícula de 7×7 con seis regiones de heptominó y una región disjunta. También son posibles cuadrículas más grandes o formas irregulares diferentes (bajo varios nombres como Suguru , Tectonic , Jigsaw Sudoku , etc.). The Times ofrece un "Dodeka Sudoku" de cuadrícula de 12×12 con 12 regiones de 4×3 cuadrados. Dell Magazines publica periódicamente rompecabezas "Number Place Challenger" de 16×16 (que utilizan los números del 1 al 16 o las letras AP). Nikoli ofrece colosos "Sudoku the Giant" de 25×25. En 2010 se publicó un rompecabezas de cuadrícula de 100 × 100 denominado Sudoku-zilla. [23]
En el periódico estadounidense USA Today y en otros medios aparece una variante de 6×6 con regiones de 3×2 bajo el nombre de "Mini Sudoku" . El objetivo es el mismo que el del Sudoku estándar, pero el rompecabezas solo utiliza los números del 1 al 6. En algunos periódicos, como en algunas ediciones de The Daily Mail , ha aparecido una forma similar, para los solucionadores de rompecabezas más jóvenes, llamada "The Junior Sudoku".
Otra variante común es añadir límites a la colocación de números más allá de los requisitos habituales de filas, columnas y casillas. A menudo, el límite adopta la forma de una "dimensión" adicional; lo más común es exigir que los números en las diagonales principales de la cuadrícula también sean únicos. Los rompecabezas "Number Place Challenger" antes mencionados son todos de esta variante, al igual que los rompecabezas Sudoku X de The Daily Mail , que utilizan cuadrículas de 6x6.
La variante del sudoku asesino combina elementos del sudoku y del kakuro . Un sudoku asesino está formado por "jaulas", normalmente representadas por cuadros delineados con guiones o colores. La suma de los números de una jaula se escribe en la esquina superior izquierda de la misma y los números no se pueden repetir en una jaula.
Los rompecabezas construidos a partir de más de dos cuadrículas también son comunes. Cinco cuadrículas de 9 × 9 que se superponen en las regiones de las esquinas en forma de quincunce se conocen en Japón como Gattai 5 (cinco fusionadas) Sudoku. En The Times , The Age y The Sydney Morning Herald , esta forma de rompecabezas se conoce como Samurai Sudoku. El Baltimore Sun y el Toronto Star publican un rompecabezas de esta variante (titulado High Five) en su edición dominical. A menudo, no se colocan datos en las regiones superpuestas. También se publican cuadrículas secuenciales, a diferencia de las superpuestas, en las que los valores en ubicaciones específicas de las cuadrículas deben transferirse a otras.
Se puede jugar una versión de mesa del Sudoku con una baraja estándar de 81 cartas (véase Juego de cartas ). En mayo de 2005, The Daily Telegraph publicó un sudoku tridimensional . El Times también publica una versión tridimensional con el nombre de Tredoku. Además, una versión del cubo de Rubik en sudoku se llama Sudoku Cube .
Se han desarrollado muchas otras variantes. [24] [25] [26] Algunas son formas diferentes en la disposición de cuadrículas superpuestas de 9 × 9, como mariposa, molino de viento o flor. [27] Otras varían la lógica para resolver la cuadrícula. Una de ellas es "Mayor que Sudoku". En este, se da una cuadrícula de 3 × 3 del Sudoku con 12 símbolos de Mayor que (>) o Menor que (<) en la línea común de los dos números adyacentes. [10] Otra variante de la lógica de la solución es "Clueless Sudoku", en el que nueve cuadrículas de Sudoku de 9 × 9 se colocan cada una en una matriz de 3 × 3. La celda central de cada cuadrícula de 3 × 3 de los nueve rompecabezas se deja en blanco y forma un décimo rompecabezas de Sudoku sin ninguna celda completada; de ahí, "desorientado". [27] Se pueden encontrar ejemplos y otras variantes en el Glosario de Sudoku .
.svg/1280px-Sudoku_Puzzle_(an_automorphic_puzzle_with_18_clues).svg.png)
Esta sección se refiere al Sudoku clásico, sin tener en cuenta los sudokus de tipo rompecabezas, hiper y otras variantes. Una cuadrícula de Sudoku completa es un tipo especial de cuadrado latino con la propiedad adicional de que no hay valores repetidos en ninguno de los nueve bloques (o cajas de 3×3 celdas). [28]
Se sabe que el problema general de resolver sudokus en cuadrículas de n 2 × n 2 de bloques n × n es NP-completo . [29] Muchos algoritmos de resolución de sudokus , como el retroceso por fuerza bruta y los enlaces danzantes , pueden resolver la mayoría de los rompecabezas de 9 × 9 de manera eficiente, pero la explosión combinatoria ocurre a medida que n aumenta, lo que crea límites prácticos a las propiedades de los sudokus que se pueden construir, analizar y resolver a medida que n aumenta. Un sudoku se puede expresar como un problema de coloración de gráficos . [30] El objetivo es construir una coloración de 9 de un gráfico en particular, dada una coloración de 9 parcial.
La menor cantidad de pistas posibles para un Sudoku adecuado es 17. [31] Decenas de miles de Sudokus distintos tienen solo 17 pistas. [32]
El número de cuadrículas de solución del Sudoku clásico 9×9 es 6.670.903.752.021.072.936.960, o alrededor de6,67 × 10 21 . [33] El número de soluciones esencialmente diferentes, cuando se tienen en cuenta simetrías como rotación, reflexión, permutación y reetiquetado, es mucho menor: 5.472.730.538. [34]
A diferencia del número de cuadrículas de Sudoku completas, el número de rompecabezas de Sudoku de 9 × 9 mínimos no se conoce con precisión. (Un rompecabezas mínimo es aquel en el que no se puede eliminar ninguna pista sin perder la unicidad de la solución). Sin embargo, las técnicas estadísticas combinadas con un generador de rompecabezas muestran que existen aproximadamente (con un error relativo del 0,065 %) 3,10 × 10 37 rompecabezas mínimos y 2,55 × 10 25 rompecabezas mínimos no esencialmente equivalentes. [35]
El rompecabezas que cautiva a la nación en realidad comenzó en una pequeña revista de Nueva York.
