Sudoku

Sudoku (en xaponés: 数独, sūdoku) ye un xuegu matemáticu que s'inventó a finales de la década de 1970, aquirió popularidá en Xapón na década de 1980 y diose a conocer nel ámbitu internacional en 2005 cuando numberosos periódicos empezaron a publicar na so seición de pasatiempos.
L'oxetivu del sudoku ye rellenar una cuadrícula de 9 × 9 celdes (81 caxellos) estremada en subcuadrículas de 3 × 3 (tamién llamaes "caxes" o "rexones") coles cifres del 1 al 9 partiendo de dellos númberos yá dispuestos en delles de les celdes. Anque podríen usase colores, lletres, figures, convenir n'usar númberos pa mayor claridá, lo qu'importa, ye que sían nueve elementos estremaos, que nun se deben repitir nuna mesma fila, columna o subcuadrícula.
Un sudoku ta bien plantegáu si la solución ye única, daqué que'l matemáticu Gary McGuire demostró que nun ye posible si nun hai un mínimu de 17 cifres de pista de primeres."Laa claves matemátiques pa resolver un sudoku", en Abc, 10/01/2012. https://www.abc.es/20120110/ciencia/abci-claves-matematicas-pa-resolver-201201101327.html Un sudoku nun puede resolvese si nun hai un mínimu de 17 cifres-pista nel so entamu, yá que con menos "nun esiste una solución única". La mayor parte de les vegaes cunta con unes 25 cifres-pista. A midida que baxen les pistes, más difícil ye'l so resolución. La solución d'un sudoku siempres ye un cuadráu llatín, anque'l recíprocu polo xeneral nun ye ciertu una y bones el sudoku establez la restricción añadida de que nun se puede repitir un mesmu númberu nuna subcuadrícula.

 Historia 
Nel sieglu XVIII, el famosu matemáticu suizu, Leonhard Euler de Basilea (1707-1783), creó un sistema de probabilidaes pa representar una serie de númberu ensin repitir. Por cuenta de esto Leonhard Euler de Basilea considérase l'inventor d'esti xuegu.Erfinder des Sudoku war ein Schweizer artículu nel periodico Die Welt Die Welt

Yá en 1970 la editorial Math Puzzles and Logic Problems publicaba una seición llamada Number place polo qu'esti enigma matemáticu convertir en pasatiempos anque años más tarde perdióse nel olvidu.

En 1984 el periódicu xaponés Monthly Nikolist publicó una seición de pasatiempos llamada Sūji wa dokushin nin kagiru (数字は独身に限る) "los númberos tienen de tar solos" (lliteralmente dokushin (独身) = "célibe, solteru"). Foi Kaji Maki, presidente de Nikoli, quien-y punxo'l nome. El nome embrivir a Sūdoku (sū = númberu, doku = solo).Hestoria del Sudoku 

Empezar a conocer internacionalmente en 2005, cuando dellos periódicos empezaron a publicar como pasatiempu.
 Regles y terminoloxía 
El sudoku preséntase de normal como una tabla de 9× 9, compuesta por subtablas de 3 × 3 denominaes "rexones" (tamién se-y llamen "caxes" o "bloques").

Delles celdes yá contienen númberos, conocíos como "númberos daos" (o dacuando "pistes"). L'oxetivu ye rellenar les celdes vacíes, con un númberu en caúna d'elles, de tala forma que cada columna, fila y rexón contenga los númberos 1–9 solo una vegada.

Amás, cada númberu de la solución apaez solo una vegada en caúna de les tres "direiciones", d'ende'l "los númberos tienen de tar solos" que remembra'l nome del xuegu.

 Métodos de resolución 
Ficheru:Soduku_ejemplo_de_trazado.png
El caxellu marcáu en verde de la rexón 3 × 3 de la esquina cimera esquierda tien de contener un 7.

La estratexa pa resolver esti ruempecabeces puede considerase como la combinación de tres procesos: rastrexu, marcáu y analís.

Patrón de marcáu de puntos (segunda notación).

 Rastrexu 
Nel exemplu anterior, rastrexando a lo llargo y anchu los sietes alcontraos en cualquier llugar de la rejilla, el xugador puede esaniciar toles celdes vacíes de la esquina cimera esquierda que nun pueden contener un 7. Esto dexa namái una celda posible (marcada en verde).

 Marcáu 
El rastrexu vien atayase cuando nun pueden afayase nuevos númberos. Nesti puntu ye necesariu centrase en dalgún analís lóxicu. La mayoría atopa útil emponer esti analís por aciu el marcáu de númberos candidatos nes celdes vacíes. Hai dos notaciones populares: subíndices y puntos.

Na notación de subíndice, los númberos candidatos escribir en pequeñu nes celdes. La desventaxa ye que los ruempecabeces orixinales publicar en periódicos que davezu nun dexen demasiáu espaciu p'afaer más qu'unos pocos díxitos. Si usa esta notación, los resolutores crean, de cutiu, una copia más grande del ruempecabeces y empleguen un llapiceru afiláu.

La segunda notación ye un patrón de puntos con un puntu na esquina cimera esquierda representando un 1 y un puntu na esquina inferior derecha representando un 9. Esta notación tien como ventaya que puede usase nel ruempecabeces orixinal. Ríquese maña pal allugamientu de los puntos, porque la esistencia de puntos movíos o marques inalvertíes lleva, inevitablemente, a tracamundiu y nun son fáciles de borrar ensin añader más tracamundiu.

 Analís 
Hai dos aproximaciones principales:
 En eliminación, el progresu realizar por aciu la socesiva eliminación de númberos candidatos pa una o más celdes, hasta dexar solo una eleición. Dempués de llograr cada respuesta, tien de realizase un nuevu rastrexu (davezu comprobando l'efectu del últimu númberu). Hai una serie de táctiques d'eliminación. Una de les más comunes ye'l "borráu del candidatu non coincidente". Les celdes con idéntica configuración de númberos candidatos dizse que coinciden si la cantidá de númberos candidatos en caúna ye igual al númberu de celdes que los contienen. Esti aproximamientu puede ser desaprobada por puristes lóxicos por demasiáu ensayu y error pero puede llegar a soluciones clares y rápido.

Idealmente, precísase atopar una combinación de téuniques qu'eviten dalgunu de los inconvenientes de los elementos de riba. El recuentu de rexones, files y columnes puede resultar aburríu. Escribir númberos candidatos en celdes vacíes puede consumir demasiao tiempu. L'aproximamientu "y-si" puede ser confusa nun siendo que se sía bien entamáu. La intención de la cuestión ye atopar una téunica qu'embriva'l recuentu y el marcáu.

 Niveles de dificultá 
Los programes informáticos que resuelven sudokus pueden envalorar la dificultá que tien un humanu p'atopar la solución, basándose na complexidá de les téuniques de resolución necesaries. Esta estimación dexa a los editores afaer los sos sudokus pa persones con distinta esperiencia resolutoria. Delles versiones "en llinia" (online) tamién ufierten dellos niveles de dificultá.

 Construcción 
Un sudoku bien fechu solo puede tener una solución, que ye la correuta, pa ser consideráu sudoku. Esto ye, un sudoku tien solución única. G. Mcguire cree probar qu'un cuadráu llatín con menos de 17 pistes necesariamente va tener múltiples soluciones (si tener). Esto ye, pa ser bien plantegáu ye condición necesaria qu'un sudoku tenga de tener siquier 17 pistes.

La construcción d'un sudoku puede ser realizada a mano eficientemente predeterminando les posiciones de los númberos daos y asignándo-yos valores pa realizar un procesu deductivu.

Los sudokus Nikoli constrúyense a mano, y el nome del autor apaez nos creitos xunto a cada ruempecabeces; los númberos daos siempres s'atopen en forma d'un patrón simétricu. Los ruempecabeces Number Place Challenger de Dell (vease Variantes más embaxo) tamién citen los creitos del autor. Los ruempecabeces sudoku qu'apaecen na mayoría de los periódicos del Reinu Xuníu aparentemente son xeneraos por ordenador, pero empleguen probables en sudokus xeneraos por ordenador. El desafíu pa los programadores de sudokus ye enseñar a un programa cómo construyir ruempecabeces intelixentes, de manera que non puedan estremase d'aquellos realizaos por humanos; Wayne Gould precisó retocar el so popular programa mientres seis años pa creer qu'algamara esi nivel.

 Variantes 
Anque lo más común ye que la tabla tenga un tamañu de 9x9 con rexones de 3x3, hai numberoses variantes. Los xuegos de iniciación pueden ser tables de 4x4 con rexones de 2x2; sol nome de Logi-5, publicáronse tables de 5x5 con pentominós como rexones; el World Puzzle Championship publicó una tabla de 6x6 con rexones de 2x3 y una tabla de 7x7 formada por 6 rexones compuestes por heptominós y una rexón separada. Tamién pueden atopase tables de mayor tamañu. El diariu The Times propón el Dodeka Sudoku, una tabla de 12x12 con 12 rexones de 4x3. Dell Magazines publica con frecuencia xuegos de 16x16 (la variante de 16x16 utiliza de normal los símbolos del 1 a la G, en llugar de los símbolos del 0 a la F usaos n'hexadecimal). L'editor de puzzles Nikoli propón el Sudoku Xigante de 25x25.

Otra variante frecuente ye añader llendes nel allugamientu de los númberos amás de caltener los requisitos normales sobre files, columnes y rexones. Con frecuencia, les llendes tomen la forma d'una dimensión extra; lo más común ye obligar a que los númberos de la diagonal principal de la tabla sían únicos. Los yá mentaos xuegos Number Place Challenger inclúin esta variante. Tamién formen parte d'esta variante los xuegos del Daily Mail qu'utilicen tables de 6x6.

El periódicu americanu USA Today publica otra variante denomada “Mini Sudoku”, consistente nuna tabla de 6x6 con rexones de 3x2. L'oxetivu ye'l mesmu que nel Sudoku orixinal, pero nesta variante solo utilícense númberos del 1 al 6.

Otra variante ye la combinación del Sudoku y el Kakuro nuna tabla de 9x9, denomada Sudoku de Sumes Cruzaes, na que les pistes danse al traviés de sumes cruzaes. Tamién ye posible que les pistes dar por aciu criptoaritmos nos que cada lletra representa un únicu díxitu del 0 al 9. Un exemplu ye: NUMBER+NUMBER=KAKURO que la so única solución ye 186925+186925=373850. Otru exemplu ye SUDOKU=IS*FUNNY que la so solución ye 426972=34*12558.


El Addoku combina elementos de Sudoku y Kakuro – de normal nun se dan númberos iniciales, sinón que la tabla de 9x9 estremar en rexones, caúna de les cuales contién la suma de tolos númberos de la rexón teniendo amás en cuenta que nun hai númberos repitíos na mesma rexón. A la de completar la tabla caltiénense amás les regles del Sudoku orixinal.

Una de les variantes más populares ye'l Hypersudoku. Publicar en periódicos y revistes de tol mundu y tamién ye conocíu por Sudoku NRC Handelsblad”, “Windoku”, “Hiper-Sudoku” y “Sudoku 4 cuadros”. La base ye idéntica a la del Sudoku orixinal, pero inclúi árees interiores adicionales nes que tienen d'apaecer númberos del 1 al 9. L'algoritmu que lu resuelve ye llixeramente distintu del Sudoku normal pola influencia de los cuadros asolapaos. Esti solapamiento da al xugador más información que dexa amenorgar les posibilidaes de los restantes cuadros. La forma de xugar ye similar a la del Sudoku pero ye necesariu poner más atención a los cuadros y a les zones asolapaes qu'a les files y columnes.

Tamién son comunes los xuegos construyíos a partir de múltiples tables de Sudoku. En Xapón ye conocíu'l Sudoku Gattai 5 (amiestu de 5) compuestu por 5 tables de 9x9 con solapamiento nes rexones de les esquines con forma de quincuncio. En diarios como The Times o The Sydney Morning Herald, esta variante conozse como Sudoku Samurai. Otros como'l Baltimore Sun y el Toronto Star publiquen esta variante na so edición dominical col nome High Five. Con frecuencia, nun s'apurren pistes nes rexones asolapaes. Tamién se publicar variantes con tables secuenciales, en llugar d'asolapaes, nes que los valores de determinaes posiciones tresferir d'una tabla a otra.

El Sudoku Social ye una versión dixital multixugador de Sudoku que dexa a 2 xugadores xugar coles mesmes sobre'l mesmu tableru. Esta variante foi creada por Crosswords Ltd. en 2010 y llanzada como aplicación pa la plataforma iOS d'Apple al traviés de la so Game Center. El Sudoku Social concede puntos a cada xugador a midida que van asitiando los númberos correutamente, bloquiando'l cuadru escoyíu al otru xugador. Les xugaes incorreutes faen que'l xugador nun tenga accesu al tableru mientres 10 segundos, amás de provocar la perda de puntos.

Tamién surdieron variantes alfabétiques, llamaes dacuando Sudokus de lletres (Wordokus): nun esiste diferencia funcional nun siendo que les lletres formen pallabres. Delles variantes, como la de TV Guide, inclúin una vegada resueltu'l xuegu una pallabra na diagonal principal, nuna fila o nuna columna; determinar la pallabra por adelantao puede ser una ayuda pal resolución del xuegu. Un Wordoku puede contener otres pallabres amás de la pallabra principal. Como nel exemplu de la derecha, les pallabres “Kari”, “Park” y “Per” podríen formar parte de la solución. Esto tendría d'evitase sustituyendo, por casu, el calter “R” pol calter “Q”. Per otru llau el Sudoku Ripeto dexa repitir símbolos y el Custom Sudoku amosar pallabres nel tableru antes de la resolución.

Con una embaraxa estándar de 81 cartes del xuegu Set!  puede xugase al Sudoku. La versión tridimensional del Sudoku foi inventada por Dion Church y publicada nel Daily Mail Telegraph en mayu de 2005. Tamién esiste una versión del cubu de Rubik denomada'l cuboku.

Hai otres munches variantes. Dalgunes presenten distintes formes na disposición de los solapamientos de tables de 9x9, tales como una caparina, un molín o una flor. Otres versiones varien na lóxica de resolución del xuegu. Una d'elles ye Sudoku Mayor que. Nesta versión, cada rexón de 3x3 contién 12 símbolos de mayor (>) o menor (<) na llinia común de dos númberos axacentes. Otra variante d'esti tipu ye Sudoku Ensin pistes nel que s'asitien nueve tables de Sudoku de 9x9 nuna matriz de 3x3. La celda central de cada rexón de 3x3 en caúna de les 9 tables dexar en blancu, formando un décimu Sudoku ensin nenguna celda completa; d'ende'l nome "ensin pistes".

 Ver tamién 
 Cuadráu máxicu

 Referencies 

 Enllaces esternos 

 – Enllaces rellacionaos colos sudokus

Categoría:Pasatiempos
Categoría:Problemes NP-completos