Sudoku ( / s uː ˈ d oʊ k uː , - ˈ d ɒ k -, s ə -/ ; japonés :数独, romanizado : sūdoku , iluminado. 'dígito único'; originalmente llamado Número Lugar ) [1] es un rompecabezas de colocación de números [2] [3] combinatorio [4] basado en lógica . En el Sudoku clásico, el objetivo es llenar una cuadrícula de 9 × 9 con dígitos de manera 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") contiene todos los dígitos del 1 al 9. El creador de rompecabezas proporciona una cuadrícula parcialmente completa, que para un rompecabezas bien planteado tiene una única solución.
Los periódicos franceses publicaron variaciones de los Sudoku en el siglo XIX, y el rompecabezas ha aparecido desde 1979 en libros de rompecabezas con el nombre de Number Place. [5] Sin embargo, el Sudoku moderno no comenzó a ganar gran popularidad hasta 1986, cuando fue publicado por la empresa japonesa de rompecabezas Nikoli con el nombre de 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 informático para producir rápidamente rompecabezas únicos.
Los acertijos numéricos aparecieron en los periódicos a finales del siglo XIX, cuando los creadores de acertijos franceses comenzaron a experimentar con la eliminación de números de los cuadrados mágicos . Le Siècle , un diario de París, 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 , perfeccionó 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 para que cada fila, columna y diagonales rotas contuvieran solo los números del 1 al 9, pero no marcaran los subcuadrados. Aunque no estaban marcados, cada subcuadrado de 3 × 3 comprendía 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 acertijos semanales fueron una característica de los periódicos franceses como L'Écho de Paris durante aproximadamente una década, pero desaparecieron durante la Primera Guerra Mundial . [9]
El Sudoku moderno probablemente fue diseñado 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 contribuyentes en las ediciones de Dell Pencil Puzzles y Word Games que incluían Number Place y siempre estuvo ausente en las ediciones que no lo incluí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 con alguno de los periódicos franceses enumerados 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, más informalmente, 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 las principales publicaciones periódicas japonesas, como el Asahi Shimbun .
En 1997, el juez de Hong Kong Wayne Gould vio un rompecabezas a medio terminar en una librería japonesa. Durante seis años, desarrolló un programa informático para producir rápidamente rompecabezas únicos. [5] Sabiendo que los periódicos británicos tienen una larga historia de publicación de crucigramas y otros acertijos, promovió el Sudoku en The Times en Gran Bretaña, que lo lanzó el 12 de noviembre de 2004 (llamándolo Su Doku). La primera carta al Times sobre Su Doku fue publicada al día siguiente, 13 de noviembre, por Ian Payn de Brentford , quejándose de que el rompecabezas le había hecho perder su parada en el metro . [12] Los Sudokus se extendieron rápidamente a otros periódicos como artículo habitual. [5] [13]
El rápido ascenso del Sudoku en Gran Bretaña desde una relativa oscuridad a un artículo de primera plana en los periódicos nacionales atrajo comentarios en los medios y parodias (como cuando la sección G2 de The Guardian se anunció como el primer suplemento periodístico 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. Desde julio de 2005, Channel 4 incluyó un juego de Sudoku diario en su servicio de teletexto . El 2 de agosto, la guía de programas 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 Sudoku televisivo en vivo del mundo, Sudoku Live , fue un concurso de rompecabezas transmitido 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 los 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. El público en casa participó en una competición interactiva separada, que ganó 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, sólo utilizó rompecabezas de 4×4 y 6×6. Se produjeron cuatro temporadas antes de que terminara el programa en 2007.
En 2006, un sitio web de Sudoku publicó la canción tributo al Sudoku del compositor Peter Levy, [16] pero rápidamente tuvo que eliminar el archivo MP3 debido al intenso tráfico. Las radios británica y australiana recogieron la canción, que aparecerá en [ when? ] en un documental de Sudoku realizado en Gran Bretaña. La embajada japonesa también nominó la canción para un premio, y Levy está 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, apenas dos semanas después de que Apple Inc. estrenara la App Store en línea dentro de su iTunes Store el 11 de julio de 2008, ya se encontraban en ella 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 con Sudoku es Brain Age: ¡entrena tu cerebro en minutos al día! . Bien recibido crítica y comercialmente, generó elogios especiales por su implementación del 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 de Brain Age titulado Brain Age 2 , que tiene más de 100 nuevos Sudokus y otras actividades.
En junio de 2008, un juicio con jurado relacionado con las drogas en Australia que costó más de 1 millón de dólares australianos fue abortado cuando se descubrió que cuatro o cinco de los doce miembros del jurado 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 variaciones. Los rompecabezas de muestra pueden ser cuadrículas de 4×4 con regiones de 2×2; Se han publicado cuadrículas de 5 × 5 con regiones pentominó con 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 heptomino y una región disjunta. También son posibles cuadrículas más grandes o diferentes formas irregulares (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 cuadrados de 4 × 3. Dell Magazines publica periódicamente acertijos de 16 × 16 "Number Place Challenger" (utilizando los números del 1 al 16 o las letras AP). Nikoli ofrece gigantes "Sudoku the Giant" de 25×25. En 2010 se publicó un rompecabezas de cuadrícula de 100 × 100 denominado Sudoku-zilla .
Bajo el nombre "Mini Sudoku", aparece en el periódico estadounidense USA Today y en otros lugares una variante de 6×6 con regiones de 3×2. El objeto es el mismo que el del Sudoku estándar, pero el rompecabezas sólo utiliza los números del 1 al 6. Una forma similar, para los solucionadores de rompecabezas más jóvenes, llamada "El Sudoku Junior", ha aparecido en algunos periódicos, como algunas ediciones de El Daily Mail .
Otra variante común es agregar límites en la ubicación de números más allá de los requisitos habituales de filas, columnas y cuadros. A menudo, el límite adopta la forma de una "dimensión" extra; lo más común es exigir que los números en las diagonales principales de la cuadrícula también sean únicos. Los acertijos "Number Place Challenger" antes mencionados son todos de esta variante, al igual que los acertijos Sudoku X en The Daily Mail , que utilizan cuadrículas de 6 × 6.
La variante Killer Sudoku combina elementos de Sudoku y Kakuro . Un sudoku espectacular se compone de "jaulas", normalmente representadas por cuadros delineados con guiones o colores. La suma de los números en una jaula está escrita en la esquina superior izquierda de la jaula y los números no se pueden repetir en una jaula.
También son comunes los rompecabezas construidos a partir de más de dos cuadrículas. Cinco cuadrículas de 9 × 9 que se superponen en las regiones de las esquinas en forma de quincunx se conocen en Japón como Sudoku Gattai 5 (cinco fusionados). 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 acertijo de esta variante (titulado High Five) en su edición dominical. A menudo, no se colocan datos dados en las regiones superpuestas. También se publican cuadrículas secuenciales, a diferencia de las superpuestas, y 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 un mazo estándar de 81 cartas (ver Juego conjunto ). En mayo de 2005 se publicó un Sudoku tridimensional en The Daily Telegraph. The Times también publica una versión tridimensional con el nombre de Tredoku. Además, una versión Sudoku del Cubo de Rubik recibe el nombre de Sudoku Cube .
Se han desarrollado muchas otras variantes. [24] [25] [26] Algunas tienen diferentes formas en la disposición de cuadrículas superpuestas de 9 × 9, como mariposas, molinos de viento o flores. [27] Otros varían la lógica para resolver la cuadrícula. Uno de ellos es "Más grande que el Sudoku". En este, se proporciona 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 el "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 en cada cuadrícula de 3 × 3 de los nueve rompecabezas se deja en blanco y forma un décimo Sudoku sin completar ninguna celda; por lo tanto, "despistado". [27] Una nueva variante combina el Sudoku con el rompecabezas de fichas deslizantes en Sudoku Slide Extreme. En esta variante, se completan todas las posiciones. Las fichas se mueven a la posición adecuada para resolver el rompecabezas. Esta variante contiene potenciadores y un modo de campaña. [ cita requerida ] 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 las variantes jigsaw, hyper y otras.
Una cuadrícula de Sudoku completa es un tipo especial de cuadrado latino con la propiedad adicional de no repetir valores en ninguno de los nueve bloques (o cuadros de celdas de 3×3). La relación entre ambas teorías es conocida, luego de comprobarse que una fórmula de primer orden que no menciona bloques es válida para Sudoku si y sólo si lo es para cuadrados latinos. [28]
Se sabe que el problema general de resolver Sudoku en n 2 × n 2 cuadrículas de n × n bloques es NP-completo . [29] Muchos algoritmos informáticos , como los enlaces de retroceso y baile , pueden resolver la mayoría de los acertijos de 9 × 9 de manera eficiente, pero la explosión combinatoria ocurre a medida que n aumenta, creando límites a las propiedades de los Sudokus que pueden construirse, analizarse y resolverse 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 particular, dada una coloración de 9 parcial.
La menor cantidad de pistas posibles para un Sudoku adecuado es 17 (probado en enero de 2012 y confirmado en septiembre de 2013). [31] [32] Se han encontrado un total de 49.158 Sudokus con 17 pistas, muchos de ellos por entusiastas japoneses. [33] [34] Se han encontrado Sudokus con 18 pistas y simetría rotacional, y hay al menos un Sudoku que tiene 18 pistas, exhibe simetría diagonal bidireccional y es automórfico . El número máximo de pistas que se pueden proporcionar sin llegar a una solución única es cuatro menos que una cuadrícula completa (77); Si faltan dos instancias de dos números cada una en las celdas que ocupan las esquinas de un rectángulo ortogonal, y exactamente dos de estas celdas están dentro de una región, los números se pueden asignar de dos maneras. Dado que esto se aplica a los cuadrados latinos en general, la mayoría de las variantes del Sudoku tienen el mismo máximo.
El número de cuadrículas de soluciones de Sudoku clásicas de 9 × 9 es 6.670.903.752.021.072.936.960 (secuencia A107739 en OEIS ), o alrededor6,67 × 10 21 . Esto es aproximadamente1,2 × 10 −6 veces el número de cuadrados latinos de 9 × 9. [35] También se han enumerado varios otros tamaños de cuadrícula; consulte el artículo principal para obtener más detalles. Se demostró que el número de soluciones esencialmente diferentes, cuando se tienen en cuenta simetrías como rotación, reflexión, permutación y reetiquetado, es solo 5.472.730.538 [36] (secuencia A109741 en el OEIS ).
A diferencia del número de cuadrículas de Sudoku completas, el número de Sudoku mínimos de 9 × 9 no se conoce con precisión. (Un acertijo mínimo es aquel en el que no se puede eliminar ninguna pista sin perder la singularidad de la solución). Sin embargo, las técnicas estadísticas combinadas con un generador de acertijos [37] muestran que aproximadamente (con un error relativo del 0,065 %) 3,10 × 10 37 acertijos mínimos y existen acertijos mínimos no esencialmente equivalentes de 2,55 × 10 25 .
El enigma que afecta a la nación en realidad comenzó en una pequeña revista de Nueva York.
Cualquier regla de resolución sin bloques ya es válida en la teoría de los cuadrados latinos extendida a los candidatos ". Reformulado más explícitamente en la segunda edición, p. 86, como: "una fórmula sin bloques es válida para Sudoku si y sólo si es valido para cuadrados latinos
