Sudokus

Un rompecabezas típico de Sudoku

La solución al rompecabezas anterior

Sudoku (Japón) ., romanizado: sūdoku, iluminado.'digit-single'; originalmente llamado Número de lugar) es un rompecabezas de número basado en la lógica y combinatorio. En Sudoku clásico, el objetivo es llenar una rejilla 9 × 9 con dígitos para que cada columna, cada fila, y cada uno de los nueve subgridos 3 × 3 que componen la rejilla (también llamada "boxes", "blocks", o "regiones") contenga todos los dígitos del 1 al 9. El dispositivo de rompecabezas proporciona una cuadrícula parcialmente completa, que para un rompecabezas bien presentado tiene una sola solución.

Los periódicos franceses presentaban variaciones de los rompecabezas de Sudoku en el siglo XIX, y el rompecabezas ha aparecido desde 1979 en los libros de rompecabezas bajo el nombre Number Place. Sin embargo, el Sudoku moderno sólo comenzó a ganar popularidad generalizada en 1986 cuando fue publicado por la compañía de rompecabezas japonesa Nikoli bajo el nombre de Sudoku, que significa "número único". Primero apareció en un periódico estadounidense, y luego The Times (Londres), en 2004, gracias a los esfuerzos de Wayne Gould, quien diseñó un programa informático para producir rápidamente rompecabezas únicos.

Historia

Predecesores

Los rompecabezas de números aparecieron en los periódicos a finales del siglo XIX, cuando las máquinas de rompecabezas francesas comenzaron a experimentar con la eliminación de números de cuadrados mágicos. Le Siècle, un diario de París, publicó un cuadrado mágico 9×9 parcialmente completado con 3×3 subsquares el 19 de noviembre de 1892. No era un Sudoku porque contenía números de dos dígitos y requería aritmética más que lógica para resolver, pero compartió características clave: cada fila, columna, y subsquare añadido hasta el mismo número.

El 6 de julio de 1895, Le Siècle's rival, La France, refina el rompecabezas de modo que era casi un Sudoku moderno y lo nombró carré magique diabolique ('cuadra de magia diabólica'). Simplificaba el rompecabezas cuadrado mágico 9×9 de modo que cada fila, columna y diagonales rotos contenían sólo los números 1–9, pero no marcaban los subsquares. Aunque no fueron marcados, cada subsquare 3×3 de hecho comprendía los números 1–9, y la limitación adicional en las diagonales rotas condujo a sólo una solución.

Estos rompecabezas semanales fueron una característica de los periódicos franceses como L'Écho de Paris durante una década, pero desapareció sobre el tiempo de la Primera Guerra Mundial.

Moderno Sudoku

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). Sudokus). Garns' Su nombre siempre estuvo presente en la lista de colaboradores en las ediciones de Dell Pencil Puzzles and Word Games que incluían Number Place y siempre estuvo ausente en las ediciones que no lo incluían. Murió en 1989 antes de tener la oportunidad de ver su creación como un fenómeno mundial. 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 empresa de rompecabezas Nikoli, en el periódico Monthly Nikolist de abril de 1984 como Sūji wa dokushin ni kagiru (数字は独身に限る), que se puede traducir como & #34;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. "Sudoku" es una marca registrada en Japón y el rompecabezas generalmente se conoce como Number Place (ナンバープレース , Nanbāpurēsu) o, más informalmente, una abreviación 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.

Difundir fuera de Japón

En 1997, el juez de Hong Kong Wayne Gould vio un rompecabezas a medio completar en una librería japonesa. Durante seis años, desarrolló un programa informático para producir rápidamente rompecabezas únicos. Sabiendo que los periódicos británicos tienen una larga trayectoria en la 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 a The Times sobre Su Doku fue publicada al día siguiente, el 13 de noviembre, por Ian Payn de Brentford, quejándose de que el rompecabezas le había hecho perder su parada en el metro. Los sudokus se extendieron rápidamente a otros periódicos como artículo habitual.

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 The Guardian's G2 se anunció como el primer suplemento de periódico con una cuadrícula de Sudoku en cada página). 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 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 el The Conway Daily Sun (New Hampshire), en 2004.

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 competencia 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, pero rápidamente tuvo que eliminar el archivo MP3 debido al intenso tráfico. La radio británica y australiana recogió la canción, que aparecerá 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.

El software 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. inauguró 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 y vendió más de 8 millones de copias en todo el mundo. Debido a su popularidad, Nintendo creó un segundo juego Brain Age titulado Brain Age², 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.

Variantes

A nonomino o jigsaw Sudoku, como se ve en El Sunday Telegraph

Y su solución (números rojos)

Variaciones de tamaños de cuadrícula o formas de región

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 pentomino bajo el nombre 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 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 12×12. con 12 regiones de 4×3 cuadrados. Dell Magazines publica periódicamente "Number Place Challenger" rompecabezas (usando los números del 1 al 16 o las letras A-P). Nikoli ofrece 25×25 "Sudoku el Gigante" gigantes. En 2010 se publicó un rompecabezas de cuadrícula de 100 × 100 denominado Sudoku-zilla.

Mini Sudoku

Bajo el nombre "Mini Sudoku", una variante 6×6 con regiones 3×2 aparece en el periódico americano USA Hoy y en otros lugares. El objeto es el mismo que el de Sudoku estándar, pero el rompecabezas sólo utiliza los números 1 a 6. Una forma similar, para los solvers más jóvenes de los rompecabezas, llamada "The Junior Sudoku", ha aparecido en algunos periódicos, como algunas ediciones de El correo diario.

Imponer restricciones adicionales

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 toma 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. El ya mencionado "Number Place Challenger" Los rompecabezas son todos de esta variante, al igual que los rompecabezas Sudoku X en The Daily Mail, que utilizan cuadrículas de 6×6.

Sudoku asesino

Un rompecabezas asesino Sudoku

Y su solución

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.

Otras variantes

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

Una versión de la mesa de Sudoku se puede jugar con una cubierta estándar de 81 tarjetas Set (ver Juego de juego). Un rompecabezas tridimensional de Sudoku fue publicado en El Daily Telegraph en mayo de 2005. The Times También publica una versión tridimensional bajo el nombre de Tredoku. Además, una versión de Sudoku del Cubo Rubik se llama Sudoku Cube.

Se han desarrollado muchas otras variantes. Algunas tienen diferentes formas en la disposición de cuadrículas superpuestas de 9 × 9, como mariposas, molinos de viento o flores. 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. Otra variante de la lógica de la solución es el "Sudoku despistado", 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". 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. Se pueden encontrar ejemplos y otras variantes en el Glosario de Sudoku.

Matemáticas de Sudoku

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.

El problema general de resolver Sudokus en n²×n² cuadrículas de n Se sabe que ×n bloques son NP-completos. Muchos algoritmos informáticos, como los enlaces de retroceso y de 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, lo que crea límites 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. 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). Se han encontrado un total de 49.158 Sudokus con 17 pistas, muchos de ellos realizados por entusiastas japoneses. 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 el OEIS), o alrededor de 6.67×10²¹. Esto es aproximadamente 1.2 ×10⁻⁶ veces el número de cuadrados latinos de 9×9. También se han enumerado 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 (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 unicidad de la solución). Sin embargo, las técnicas estadísticas combinadas con un generador de acertijos muestran que aproximadamente (con un error relativo del 0,065%) 3,10 × 10³⁷ existen acertijos mínimos y acertijos mínimos de 2,55 × 10²⁵ no esencialmente equivalentes.

Competiciones

• El primer Campeonato Mundial de Sudoku se celebró en Lucca, Italia, del 10 al 11 de marzo de 2006. El ganador fue Jana Tylová de la República Checa. La competencia incluyó numerosas variantes.
• El segundo Campeonato Mundial de Sudoku se celebró en Praga, República Checa, del 28 de marzo al 1 de abril de 2007. El campeón individual era Thomas Snyder de los Estados Unidos. El campeón del equipo era Japón.
• El tercer Campeonato Mundial de Sudoku se celebró en Goa, India, del 14 al 16 de abril de 2008. Thomas Snyder repitió como el campeón general individual y también ganó el primer Trofeo Clásico (un subconjunto de la competencia contando sólo Sudoku clásico). La República Checa ganó el concurso de equipo.
• El cuarto Campeonato Mundial de Sudoku se celebró en Žilina, Eslovaquia, del 24 al 27 de abril de 2009. Después del pasado campeón Thomas Snyder de los EE.UU. ganó la calificación general, Jan Mrozowski de Polonia surgió de un playoff de 36 competidores para convertirse en el nuevo campeón mundial de Sudoku. La nación anfitriona Eslovaquia surgió como el primer equipo en una competencia separada de los escuadrones de tres miembros.
• El quinto Campeonato Mundial de Sudoku se celebró en Filadelfia, Pennsylvania, del 29 de abril al 2 de mayo de 2010. Jan Mrozowski de Polonia defendió exitosamente su título mundial en la competencia individual, mientras que Alemania ganó un evento de equipo separado. Los rompecabezas fueron escritos por Thomas Snyder y Wei-Hwa Huang, ambos pasados campeones de U.S. Sudoku.
• El 12o Campeonato Mundial de Sudoku (WSC) se celebró en Bangalore, India, del 15 al 22 de octubre de 2017. Kota Morinishi de Japón ganó el WSC Individual y China ganó el evento del equipo.
• El 13o Campeonato Mundial de Sudoku tuvo lugar en la República Checa.
• En los Estados Unidos, el Campeonato Nacional Sudoku Inquirer de Filadelfia se ha celebrado tres veces, cada vez que ofrece un premio de $10.000 al ganador de la división avanzada y un lugar en el equipo nacional de Sudoku de los Estados Unidos que viaja a los campeonatos mundiales. Los ganadores del evento fueron Thomas Snyder (2007), Wei-Hwa Huang (2008) y Tammy McLeod (2009). En el evento de 2009, el tercer finalista en la división avanzada, Eugene Varshavsky, realizó muy mal en el escenario después de establecer un tiempo de calificación muy rápido en el papel, que llamó la atención de organizadores y competidores incluyendo el campeón pasado Thomas Snyder, que pidió a los organizadores reconsiderar sus resultados debido a la sospecha de engaño. Tras una investigación y una prueba de Varshavsky, los organizadores lo descalificaron y adjudicaron el tercer lugar a Chris Narrikkattu.