Sudoku

Archiu:Sudoku Puzzle by L2G-20050714 standardized layout.svg

Sudoku

Archiu:Sudoku-by-L2G-20050714.svg

Eixemple de sudoku

Archiu:Sudoku resuelto completo.png

Sudoku resolt

Sudoku (en japonés: 数独, sūdoku) és un joc matemàtic que es va inventar a finals de la década de 1970, va adquirir popularitat en Japó en la década de 1980, i es va donar a conéixer en l'àmbit internacional en 2005, quan numerosos periòdics varen escomençar a publicar-ho en la seua secció de pasatiempos.

L'objectiu del sudoku és reblir una cuadrícula de 9 × 9 celes (81 caselles) dividida en subcuadrículas de 3 × 3 (també cridades «caixes» o «regions») en les sifres de l'1 al 9 partint d'alguns números ya disposts en algunes de les celes. La forma inicial del joc és que siguen nou elements diferenciats, que no es deuen repetir en una mateixa fila, columna o subcuadrícula. Un sudoku ben plantejat solament pot tindre una solució, i ha de tindre a lo manco 17 pistes inicials. La solució d'un sudoku sempre és un quadrat llatí, encara que el recíproc en general no és cert ya que el sudoku establix la restricció afegida de que no es pot repetir un mateix número en una subcuadrícula.

Història

En el XVIII el famós matemàtic suís Leonhard Euler va crear un sistema de provabilitats per a representar una série de números sense repetir. Per açò, Euler es considera l'inventor d'este joc.

Ya en 1970 l'editorial Math Puzles and Logic Problems publicava una secció anomenada Number plau per lo que este enigma matemàtic es convertiria en pasatiempos encara que anys més vesprada es va perdre en l'oblit.

En 1984 el periòdic japonés Monthly Nikolist va publicar una secció de pasatiempos cridada Sūji wa dokushin ni kagiru (数字は独身に限る) «els números deuen ser únics» (lliteralment dokushin (独身) = «célibe, fadrí»). Va ser Maki Kaji, president de Nikoli, qui li va posar el nom. El nom es va abreviar a Sūdoku (sū = número, doku = solament).

Es va començar a conéixer internacionalment en 2005, quan varis periòdics varen escomençar a publicar-ho com pasatiempo.

Regles i terminologia

El sudoku es presenta habitualment com una taula de 9 × 9, composta per subtablas de 3 × 3 denominades «regions» (també se li criden «caixes» o «blocs»).

Algunes celes ya contenen números, coneguts com a «números donats» (o a voltes «pistes»). L'objectiu és reblir les celes buides, en un número en cada una d'elles, de tal forma que cada columna, fila i regió continga els números 1–9 solament una volta.

Ademés, cada número de la solució apareix solament una volta en cada una de les tres «direccions», d'ahí el «els números deuen estar sols» que evoca el nom del joc.

Métodos de resolució

Archiu:Soduku ejemplo de trazado.png

La casella marcada en vert de la regió 3 × 3 del cantó superior esquerre deu contindre un 7.

L'estratègia per a resoldre este rompecabezas es pot considerar com la combinació de tres processos: rastreig, marcat i anàlisis.

Archiu:Sudoku dot notation.png

Patró de marcat de punts (segona notació)

Rastreig

En l'eixemple anterior, rastrejant a lo llarc i ample els sietes localisats en qualsevol lloc de la reixeta, el jugador pot eliminar totes les celes buides del cantó superior esquerra que no poden contindre un 7. Açò deixa només una cela possible (marcada en vert).

Marcat

El rastreig ve a interrompre's quan no poden descobrir-se nous números. En este punt és necessari centrar-se en algun anàlisis llògic. La majoria troba útil guiar este anàlisis per mig del marcat de números candidats en les celes buides. Hi ha dos notacions populars: subíndexs i punts.

En la notació de subíndex, els números candidats s'escriuen en chicotet en les celes. La desventaja és que els rompecabezas originals es publiquen en periòdics que habitualment no deixen massa espai per a acomodar més que uns pocs dígits. Si s'usa esta notació, els resolutores creen, a sovint, una còpia més gran del rompecabezas i ampren un llapis esmolat.

La segona notació és un patró de punts en un punt en el cantó superior esquerre representant un 1 i un punt en el cantó inferior dret representant un 9. Esta notació té com a ventaja que pot usar-se en el rompecabezas original. Es requerix destrea per a l'emplaçament dels punts, perque l'existència de punts desplaçats o marques inadvertides du, inevitablement, a confusió i no són fàcils de borrar sense afegir més confusió.

Anàlisis

Hi ha dos aproximacions principals:

• En eliminació, el progrés es realisa per mig de la successiva eliminació de números candidats per a una o més celes, fins a deixar solament una elecció. Despuix de conseguir cada resposta, deu realisar-se un nou rastreig (habitualment comprovant l'efecte de l'últim número). Hi ha una série de tàctiques d'eliminació. Una de les més comunes és el «borrat del candidat no coincidente». Les celes en idèntica configuració de números candidats es diu que coincidixen si la cantitat de números candidats en cada una és igual al número de celes que els contenen. Esta aproximació pot ser desaprovada per puristes llògics per massa ensaig i error pero pot aplegar a solucions clares i ràpidament.

Idealment, es necessita trobar una combinació de tècniques que eviten algun dels inconvenients dels elements de dalt. El reconte de regions, files i columnes pot resultar avorrit. Escriure números candidats en celes buides pot consumir massa temps. L'aproximació «i-si» pot ser confusa a menos que se siga ben organisat. L'intenció de la qüestió és trobar una tècnica que minimise el reconte i el marcat.

En anglés es va publicar un anàlisis sustematico de la llògica i de les tècniques de resolució: «Pattern-Based Constraint Satisfaction and Logic Puzles».

Métodos bàsics analític-sistemàtics

Archiu:Sudoku-scan-and-count.svg

1. Método «Erejat»: Prendre una sifra freqüent, per eixemple «5». No es permeten més «5» en les llínees roges. L'única posició lliure en el bloc superior dret per a un «5» és, per tant, el camp marcat en vert. 2º  método «counting through»: Per al camp marcat en blau en el centre, s'eliminen tots els dígits ya especificats en la fila i columna (tots emmarcats en blau), no hi ha més en el bloc. Només queda el candidat «5» per a este camp.

Resoldre sudokus requerix un enfocament sistemàtic, i fan falta anàlisis i pensament llògic. Els sudokus fàcils a sovint poden resoldre's mentalment per mig del pensament llògic. Per a problemes més desafiants, pot ser necessari prendre notes per a registrar diferents solucions possibles per a cada camp (candidat).

En lo sucesivo, s'entén per solució analític-sistemàtica d'un sudoku la combinació de métodos que, despuix d'un examen relativament curt i clar, conduïxen a un resultat clar per a una posició prèviament no establida. Eixemples de tals métodos són la garbell (escanege), reconte i els nous procediments d'exclusió de candidats. Si totes les posicions poden decidir-se d'esta manera, llavors -en contrast en la comprovació (falsificació d'una hipòtesis)- està garantisat eixir del pas en un sol full.

Contar en unitats

• «Método dels nuets»: Primer se selecciona un camp. Per a este camp, s'exclouen tots els dígits que ya estan en la mateixa unitat (fila, columna o bloc). Si només queda un dígit, és la solució per a este camp. (Només queda un dígit per a la posició considerada.) És aconsellable escomençar per les columnes, files o blocs en menys camps buits, ya que lo més provable és que ací es puguen excloure tots els dígits menys un.
• «Método dels amagats»: En este método, s'observa una unitat (fila, columna o bloc) i un dígit que encara no s'ha introduït en esta unitat. Com cada dígit apareix exactament una volta en una unitat, deu introduir-se en un dels camps lliures. Si només hi ha un camp lliure en esta unitat en la que el dígit es pot introduir sense que es produïxca més d'una volta en una atra unitat, s'introduïx en este camp.

Visualisació de dígits

Primer se selecciona un dígit a l'encert i després es miren tots els camps ya reblits en este dígit un darrere l'atre (valors per defecte i solucions). Els demés camps de l'unitat corresponent (siga fila, columna o bloc) s'exclouen per regla. Si s'exclouen tots els camps d'una unitat llevat un, el dígit candidat del camp restant es convertix en la solució (segons el método dels amagats mencionat anteriorment). A continuació, es continua de la mateixa manera en el següent dígit.

Si introduïx (provisionalment) els dígits que encara no apareixen en les unitats respectives (fila, columna o bloc) en cada camp, podrà reconéixer els amagats pel fet de que només quede un dígit en un camp. En el cas de les amagades, el dígit en qüestió apareix exactament una volta en una unitat.

Atres métodos d'exclusió (eliminació)

Es tracta de métodos que permeten reduir encara més el conjunt candidat de camps individuals. Convé escomençar pels que només s'apliquen a una unitat. En principi, l'orde en que s'apliquen pot invertir-se.

Método Twin (Doble bessó):

• • El método Twin directe: Si en $n\ge 1$ celes d'una unitat (fila, columna o bloc) solament queden els mateixos $n$ candidats, és dir, si els conjunts de candidats d'estes celes no contenen més sifres, llavors en cada una de les $n$ celes deu haver una d'estes $n$ sifres (llevat en $n=1$, a on encara no se sap qué sifra correspon a quina cela). Per lo tant, estes sifres no poden aparéixer en cap atra cela de l'unitat afectada. Si para $n>1$ el doble bessó es troba, per eixemple, en una fila, es deuen eliminar els $n$ candidats en les celes restants d'eixa fila. De manera anàloga, açò s'aplica a la columna o bloc.
    En el doble bessó / «Doble twin» es poden inclús eliminar dos unitats al mateix temps: per eixemple, fila i bloc o columna i bloc, com es mostra en l'eixemple «Image: Patró llògic A» – Eixemple vert. Ací, per eixemple, ni el 5 ni el 9 poden aparéixer en la zona de fondo vert.

• • El método Twin indirecte (amagat): Novament es considera una unitat i es busquen $n\ge 1$ sifres que solament apareixen en exactament $n$ celes d'eixa unitat, és dir, cap d'estes sifres apareix en un atre conjunt de candidats dins d'esta unitat considerada. Llavors, en cada una de les $n$ celes deu haver una d'estes $n$ sifres, i es poden eliminar tots els demés candidats d'estes $n$ celes. Un eixemple per a $n=1$ és en l'image «en tots els candidats restants», en la fila 8, la cela g8 en les sifres 3 i 6, una configuració que elimina el 3 d'eixa cela; o per a $n=2$, la columna f en les celes f1 i f9 i les sifres 6 i 8.
    A través d'esta eliminació, el Twin indirecte es convertix en un Twin directe i es fan possibles les eliminacions de candidats descrites allí.

Método dels Triples nuets (Triple): Representa una analogia al método directe Twin. Si en $n\ge 2$ celes d'una unitat solament apareixen $n$ sifres com a candidats (açò pot ocórrer inclús en $n\ge 3$, fins al parell de sifres per cela; una configuració que també es diu «Swordfish» = peix espasa), estes $n$ sifres deuen eliminar-se d'atres celes de la mateixa unitat (fila, columna o bloc). Un eixemple són en la columna f les celes f5 i f7, lo que elimina els dos candidats 3 i 7 en totes les demés celes d'eixa columna. D'esta manera, en cada pas d'eliminació per unitat es formen llistes de candidats disjuntas; en l'eixemple, les sifres 1 i 4 en les celes f4 i f6.
En el Doble Triple les $n\le 3$ celes considerades no estan solament en una fila o columna, sino també en el mateix bloc. Llavors, estos candidats no solament poden eliminar-se en les celes restants de la mateixa fila o columna, sino també en el bloc (Eixemple: Candidats 3, 5, 7 en les celes d7–f7 en la fila 7 i en el bloc d7–f9 en l'image «en tots els candidats restants»).

El Swordfish (= peix espasa, vore també dalt): Esta estructura és molt semblada al método directe Twin, pero es tracta de celes emparellades no solament en 2, sino en 3 files/columnes, a on exactament un extrem en la columna/fila coincidix emparejadamente en un extrem d'un atre parell en la columna/fila, de modo que els extrems del tot formen una figura tancada en forma d'anell. Inclús en este cas, la sifra de candidat en les 3 columnes/files afectades està exclosa de les 7 celes restants de cada columna/fila.

El método X-Wing: La condició prèvia para açò és una disposició emparellada d'un sol candidat en dos unitats:

• • X-Wing simètric: En dos files (o columnes) una sifra de candidat apareix exclusivament en dos columnes (o files) idèntiques. Estes 4 celes deuen estar en a lo manco 2 blocs diferents, pero també poden estar en 4 blocs. Estes quatre celes possibles d'intersecció representen els cantons d'un rectàngul imaginari o formen un patró simètric en forma de X. Els verdaders punts de solució deuen estar obligatòriament en els extrems d'una de les dos diagonals possibles. En conseqüència, este candidat deu eliminar-se en els 2*7 camps restants de les dos columnes (o files) i en els camps restants dels blocs comuns.
  • X-Wing asimètric (Tipo A): En dos files (o columnes) una sifra de candidat apareix solament dos voltes. Cada una d'estes files (columnes) es troba en la mateixa columna (fila), mentres que les dos restants estan en un bloc comú. Ací es forma una figura X asimètrica. Els extrems de les possibles dos diagonals formen els punts d'un trapezi. Açò provoca una exclusió de candidats en els 7 camps restants d'una columna (o fila) comuna o dels blocs comuns (vore image: Patró llògic B eixemple roig i groc).
  • X-Wing asimètric (Tipo B): En dos files (o columnes) una sifra de candidat apareix solament dos voltes. No obstant, no hi ha una posició emparellada en una columna (fila), sino que dos d'elles es troben en els mateixos blocs. També es forma una figura X en este cas. Els extrems de les possibles dos diagonals formen els punts d'un trapezi. Açò provoca una exclusió de candidats en els 7 camps restants dels blocs comuns.

• • X-Wing asimètric (Tipo C): En dos blocs, una sifra de candidat apareix dos voltes. Cada candidat es troba en la mateixa fila (o columna). En este cas, les possibles interseccions també formen un trapezi. Açò provoca una exclusió de candidats en els dos 7 camps restants de les files (columnes) comunes (vore image: Patró llògic B eixemple roig i groc).
• Interacció de blocs: Si un candidat numèric en dos blocs disposts horisontal (o vertical)ment està exclós en una (!) fila (o columna) comuna entre els dos blocs (sense haver segut ya ingressat com a solució en els tres blocs considerats), llavors deu aparéixer com a solució en este bloc restant en esta fila, i d'esta manera està exclós en les dos files restants (o columnes) d'este bloc (comparar image: Patró llògic C eixemple rosa; encara que allí es varen considerar parells, açò també s'aplica a cada candidat individual).
• Comprovació de bloc-fila: Si en un bloc no es pot assignar de manera inequívoca una sifra candidata a una cela, pero totes les celes del bloc a on esta sifra encara és possible es troben en una sola fila (és dir, fila o columna), llavors la sifra candidata elimina totes les seues demés aparicions en la fila respectiva fora del bloc. Un eixemple de «Comprovació de bloc a fila» és la situació en el bloc d1–f3: allí, la sifra candidata 6 solament apareix en la fila 1 d'este bloc. Per lo tant, deu ser colocada en esta fila per a este bloc, per eixemple, en la cela d1 o la cela f1, i no pot aparéixer fòra d'este bloc en la fila 1, per eixemple, en les celes a1–c1 o g1–i1. De manera similar, existix una «Comprovació de bloc a columna» per a la sifra candidata 4 en les celes f4 i f6 del bloc d4-f6, lo que elimina el 4 com a candidat en les celes f1 i f3.

Nivells de dificultat

Els programes informàtics que resolen sudokus poden estimar la dificultat que té un humà per a trobar la solució, basant-se en la complexitat de les tècniques de resolució necessàries. Esta estimació permet als editors adaptar els seus sudokus per a persones en diferent experiència resolutoria. Algunes versions «en llínea» (online) també oferixen varis nivells de dificultat.^{cita requerida}

Construcció

Un sudoku deu tindre una única solució per a que es considere ben plantejat; és dir, a partir de les pistes inicials només pot haver una forma vàlida de completar les caselles restants. Per a que un sudoku posseïxca una única solució, és necessari que el número de pistes inicials siga a lo manco 17; açò es va demostrar en 2012.

La construcció d'un sudoku pot ser realisada a mà eficientemente predeterminant les posicions dels números donats i assignant-los valors per a realisar un procés deductivo.

Els sudokus Nikoli es construïxen a mà, i el nom de l'autor apareix en els crèdits junt a cada rompecabezas; els números donats sempre es troben en forma d'un patró simètric. Els rompecabezas Number Plau Challenger de Dell (vore Variants més avall) també citen els crèdits de l'autor. Els rompecabezas sudoku que apareixen en la majoria dels periòdics del Regne Unit aparentment són generats per ordenador, pero ampren provables en sudokus generats per ordenador. El desafiu per als programadors de sudokus és ensenyar a un programa cóm construir rompecabezas inteligents, de manera que no puguen distinguir-se dels realisats per humans; Wayne Gould va necessitar retocar el seu popular programa durant sis anys per a creure que havia alcançat eixe nivell.

Variants

Encara que lo més comú és que la taula tinga un tamany de 9x9 en regions de 3x3, hi ha numeroses variants. Els jocs d'iniciació poden ser taules de 4x4 en regions de 2x2; baixe el nom de Logi-5, s'han publicat taules de 5x5 en pentominós com a regions; el World Puzle Championship ha publicat una taula de 6x6 en regions de 2x3 i una taula de 7x7 formada per 6 regions compostes per heptominós i una regió separada. També es poden trobar taules de major tamany. El diari The Times propon el Dodeka Sudoku, una taula de 12x12 en 12 regions de 4x3. Dell Magazines publica en freqüència jocs de 16x16 (la variant de 16x16 sol utilisar els símbols de l'1 a la G, en lloc dels símbols del 0 a la F usats en hexadecimal). L'editor de puzles Nikoli propon el Sudoku Jagant de 25x25.

Archiu:A nonomino sudoku.svg

Un sudoku fet de nonominós (poliominós de 9 celes), com els de el The Sunday Telegraph.

Archiu:A nonomino sudoku solution.svg

La solució del puzle anterior són els números en roig.

Una atra variant freqüent és afegir llímits en la colocació dels números a banda de mantindre els requisits normals sobre files, columnes i regions. En freqüència, els llímits prenen la forma d'una «dimensió» extra; lo més comú és obligar a que els números de la diagonal principal de la taula siguen únics. Els ya mencionats jocs Number Plau Challenger inclouen esta variant. També formen part d'esta variant els jocs del Daily Mail que utilisen taules de 6x6.

El periòdic USA Today publica una atra variant denominada «Mini Sudoku», consistent en una taula de 6x6 en regions de 3x2. L'objectiu és el mateix que en el sudoku original, pero en esta variant solament s'utilisen números de l'1 al 6.

Una atra variant és la combinació del Sudoku i el Kakuro en una taula de 9x9, denominada Sudoku de Sumes Creuades, en la que les pistes es donen a través de sumes creuades. També és possible que les pistes es donen per mig de criptoaritmos en els que cada lletra representa un únic dígit del 0 al 9. Un eixemple és: NUMBER+NUMBER=KAKURO l'única solució del qual és 186925+186925=373850. Un atre eixemple és SUDOKU=IS*FUNNY la solució del qual és 426972=34*12558.

Archiu:Killersudoku color.svg

Un Sudoku Killer.

Archiu:Killersudoku color solution.svg

Solució del puzle de dalt.

l'Addoku combina elements de Sudoku i Kakuro – normalment no es donen números inicials, sino que la taula de 9x9 es dividix en regions, cada una de les quals conté la suma de tots els números de la regió tenint ademés en conte que no hi ha números repetits en la mateixa regió. A l'hora de completar la taula es mantenen ademés les regles del Sudoku original.

Una de les variants més populars és el Hypersudoku. Es publica en periòdics i revistes de tot lo món i també és conegut per «Sudoku NRC Handelsblad», «Windoku», «Hiper-Sudoku» i «Sudoku 4 quadros». La base és idèntica a la del Sudoku original, pero inclou àrees interiors adicionals en les que deuen aparéixer números de l'1 al 9. L'algoritme que ho resol és llaugerament diferent del Sudoku normal per l'influència dels quadros solapados. Este solapamiento dona al jugador més informació que permet reduir les possibilitats dels restants quadros. La forma de jugar és similar a la del Sudoku pero és necessari prestar més atenció a les quadros i a les zones solapadas que a les files i columnes.

Archiu:Wordoku puzzle.svg

Un Sudoku de lletres

Archiu:Wordoku puzzle solution.svg

La solució de l'anterior està en roig

També són comuns els jocs construïts a partir de múltiples taules de Sudoku. En Japó és conegut el Sudoku Gattai 5 (mescla de 5) compost per 5 taules de 9x9 en solapamiento en les regions dels cantons en forma de quincuncio. En diaris com The Times o The Sydney Morning Herald, esta variant es coneix com a Sudoku Samurai. Uns atres com el Baltimore Sun i el Toronto Star publiquen esta variant en la seua edició dominical en el nom High Five. En freqüència, no es proporcionen pistes en les regions solapadas. També es publiquen variants en taules seqüencials, en lloc de solapadas, en les que els valors de determinades posicions es transferixen d'una taula a una atra.

El Sudoku Social és una versió digital multijugador de Sudoku que permet a 2 jugadors jugar al mateix temps sobre el mateix tauler. Esta variant va ser creada per Crosswords Ltd. en 2010 i llançada com a aplicació per a la plataforma iOS d'Apple a través de la seua Game Center. El Sudoku Social[1] concedix punts a cada jugador a mida que van colocant els números correctament, bloquejant el quadro seleccionat a l'atre jugador. Les jugades incorrectes fan que el jugador no tinga accés al tauler durant 10 segons, ademés de provocar la pèrdua de punts.

També han sorgit variants alfabètiques, cridades a voltes Sudokus de lletres (Wordokus): no existix diferència funcional a menos que les lletres formen paraules. Algunes variants, com la de TV Guide, inclouen una volta resolt el joc una paraula en la diagonal principal, en una fila o en una columna; determinar la paraula per avant pot ser una ajuda per a la resolució del joc. Un Wordoku pot contindre atres paraules ademés de la paraula principal. Com en l'eixemple de la dreta, les paraules «Kari», «Park» i «Per» podrien formar part de la solució. Açò deuria evitar-se substituint, per eixemple, el caràcter «R» pel caràcter «Q». Per un atre costat el Sudoku Ripeto permet repetir símbols i el Custom Sudoku mostrar paraules en el tauler abans de la resolució.

Archiu:Didoku Sudoku puzzle and Solution with inscription WIKIPEDIA www.didoku.com MiguelPalomo.png

Custom Sudoku en una paraula i lletres repetides

En una baralla estàndart de 81 cartes del jugue Set! pot jugar-se al Sudoku. La versió tridimensional del Sudoku va ser inventada per Dion Church i publicada en el Daily Mail Telegraph en maig de 2005. També existix una versió del gaveta de Rubik denominada el cuboku.

Archiu:Comparison Sudoku.png

Un eixemple de Sudoku Major que.

Hi ha moltes atres variants. Algunes presenten diferents formes en la disposició dels solapamientos de taules de 9x9, tals com una palometa, un molí o una flor. Atres versions varien en la llògica de resolució del joc. Una d'elles és Sudoku Major que. En esta versió, cada regió de 3x3 conté 12 símbols de major (>) o menor (<) en la llínea comuna de dos números adjacents. Una atra variant d'este tipo és Sudoku Sense pistes en el que es coloquen nou taules de Sudoku de 9x9 en una matriu de 3x3. La cela central de cada regió de 3x3 en cada una de les 9 taules es deixa en blanc, formant un dècim Sudoku sense cap cela completa; d'ahí el nom «sense pistes».

Vore també

• Algoritmes per a la resolució de sudokus
• Quadrat màgic
• Hitori