Tipus | joc d'habilitat mental i esport mental |
---|---|
Basat en | Quadrat llatí |
Gènere | joc d'habilitat mental |
Sudoku (japonès: 数独 sūdoku; en traducció directa al català: Xifra soltera), sovint escrit també Su Doku,[1] és un trencaclosques de combinatòria[2] basat en la lògica.[3][4]
En el sudoku clàssic, l'objectiu és omplir una graella de 9×9 files i columnes subdividida en 9 subgraelles de 3×3 anomenades regions. Donats uns quants números inicials, l'objectiu és col·locar un número de l'1 al 9 en cada cel·la de tal manera que mai coincideixin dos números iguals en cada línia horitzontal, vertical o en cada regió. Els numerals en els sudoku es fan servir només per conveniència, sense que existeixi cap relació aritmètica entre ells. De fet, poden fer-se servir en qualsevol tipus de símbols, lletres, formes, colors… sense alterar-ne el funcionament.
Els diaris francesos van impulsar variacions del sudoku al segle xix, i el trencaclosques va aparèixer a partir del 1979 en llibres de trencaclosques sota el nom "Number Place".[5][6] No obstant, el sudoku modern només va començar a tenir certa popularitat a partir del 1986 quan en va publicar la companyia de trencaclosques japonesa Nikoli amb el nom sudoku.[7]
El joc va ser inventat pel matemàtic suís Leonhard Euler al segle xviii, qui va definir el concepte base d’aquests mots encreuats numèrics, en el qual cal omplir una quadrícula de blocs de 9x9 amb nou caselles en cada un en què cap columna contingui el mateix número de l’1 al 9. Però la seva popularitat no esclataria fins que l'editor japonès Maki Kaji, conegut com el “padrí dels sudoku” pel seu paper en la popularització d’aquests trencaclosques numèrics, va emprendre’n la publicació a partir de l'abril del 1984 en una secció de passatemps a la revista Monthly Nikolist, on va popularitzar el nom actual de Sudoku.[8]
A l'època moderna, però, aquest joc va reprendre's com entreteniment abans, a finals dels anys 70 als Estats Units, a la revista publicada a Nova York Math Puzzles and Logic Problems, amb el nom de Number Place.
Quan va aparèixer al Japó el 1984 a la revista Monthly Nikolist ho va fer sota el nom de Suji wa dokushin ni kagiru (数字は独身に限る), que vol dir les xifres han de ser solteres. Més endavant es va abreujar el nom a su doku, literalment xifra soltera.
El 1986 hi van introduir dues modificacions que en van millorar la popularitat: el nombre de xifres donades com a pista era menor o igual a 30, i formaven una composició simètrica respecte al punt central.
Al Japó "Sudoku" és una marca registrada per Nikoli (l'editorial de trencaclosques de Kaji), de manera que altres editors usen noms diferents per al mateix joc.
El trencaclosques és una graella de 9×9 files i columnes formada per 9 subgraelles de 3×3, anomenades regions. A l'inici del joc algunes cel·les contenen ja xifres. L'objectiu és omplir les cel·les buides amb una xifra en cadascuna d'aquestes de tal manera que cada filera, cada columna i cada regió contingui tots els numerals de l'1 al 9 només una vegada.
L'atractiu del trencaclosques recau precisament en la senzillesa de les normes si bé el raonament per resoldre'ls pot arribar a ser complex. Els sudoku es publiquen generalment valorats en termes de dificultat i sovint s'expressa també el temps aproximat de resolució. Generalment es considera que, com més números venen donats ja inicialment, més fàcil és trobar-ne la solució; el contrari no és necessàriament cert, ja que la dificultat d'un sudoku depèn principalment de la dificultat de determinar lògicament els següents números.
Alguns professors recomanen el sudoku com un exercici de raonament lògic.
L'estratègia per a resoldre un trencaclosca es pot considerar com la combinació de tres processos: escanerització, marcatge i anàlisi.
L'escanerització es realitza des del principi i periòdicament, durant tota la resolució. L'escanerització pot haver de ser executat diverses vegades entre períodes d'anàlisi. L'escanerització consta de dues tècniques bàsiques: trama creuada i recompte, que poden usar-se alternativament.
Els resoledors avançats busquen "contingències" mentre escanegen, això és, fiten la ubicació d'un nombre en una fila, columna o regió, o en dues o tres cel·les. Quan aquestes cel·les descansen totes en la mateixa fila (o columna) i regió, poden usar-se amb un propòsit d'eliminació durant la trama creuada i el recompte. Trencaclosques particularment desafiadors poden requerir el reconeixement de múltiples contingències, potser en múltiples direccions o fins i tot interseccions - relegant la majoria dels resoledors al marcat (com es descriu més avall). Els trencaclosca que poden ser resolts només mitjançant escaneig, sense requerir la detecció de contingències es classifiquen com a "fàcils"; altres de més difícils, per definició, no poden resoldre's únicament mitjançant escanerització.
L'escanerització ve a interrompre's quan no poden descobrir-se nous nombres. En aquest punt és necessari centrar-se en alguna anàlisi lògica. La major part troba útil guiar aquesta anàlisi mitjançant el marcat de nombres candidats en les cel·les buides. Hi ha dues notacions populars: subíndexs i punts. En la notació de subíndex, els nombres candidats s'escriuen en petit en les cel·les. El desavantatge és que els trencaclosca originals són publicats en periòdics que habitualment no deixen massa espai per acomodar-hi gaires dígits. Si s'usa aquesta notació, els resoledors es preparen, sovint, una còpia més gran del sudoku i empren un llapis esmolat. La segona mena de notació és un patró de punts amb un punt en el cantó superior esquerra representant un 1 i un punt en el cantó inferior dreta representant un 9. Aquesta notació té com a avantatge que pot usar-se en el sudoku original. Es requereix destresa per a l'emplaçament dels punts, perquè punts lleugerament desplaçats o fins i tot marques involuntàries duen, inevitablement, a confusió i no són fàcils d'esborrar sense afegir encara més confusió.
Hi ha dues aproximacions principals: eliminació i "i-si".
Idealment, es necessita trobar una combinació de tècniques que evitin algun dels inconvenients dels elements de dalt. El recompte de regions, files i columnes pot resultar avorrit. Escriure nombres candidats en cel·les buides pot consumir massa temps. L'aproximació "i-si" pot ser confusa llevat que hom sia ben organitzat. El quid de la qüestió és trobar una tècnica que minimitzi el recompte, el marcat i l'esborrat.
El mètode de ramificació i poda permet resoldre el trencaclosques amb una sèrie d'algorismes.[9]
Per a un programador informàtic és relativament senzill construir una cerca amb el mètode de Sudoku backtracking o "tornada enrere". El mecanisme consisteix a assignar un valor (l'1 o el més proper, per exemple) a la primera cel·la disponible (la superior esquerra, generalment) i llavors continuar assignant el següent valor disponible (seria el 2) a la següent cel·la possible. Això continuaria fins que descobrís una duplicació, en aquest cas, el següent valor alternatiu es col·locaria al primer camp alterat. En el cas que cap valor pogués complís la restricció es retrocediria a la casella anterior i es provarien altres nombres.
Encara que lluny de l'eficiència computacional, aquest mètode trobarà la solució amb bastant més temps que el següent mètode: el programa podria deixar una marca de valors potencials per a les cel·les, eliminant valors impossibles fins que només quedés un valor per una cel·la determinada. Llavors s'ompliria aquesta cel·la i s'utilitzaria aquesta informació per a més eliminacions i així successivament fins al final. Això emularia més exactament el que faria un jugador humà.
Codificar la cerca per a impossibilitats basades en contingències, i fins i tot múltiples contingències (com seria requerit per sudoku més difícils) és bastant complex de fer a mà. De totes maneres, aquestes complicacions són innecessàries si tot el que el programador vol fer és trobar la solució eficientment. Una forma més eficient de construir solucions comporta eines de programació avançada.
Alguns d'aquests programes construïts així, que emulen la resolució humana, permeten estimar la dificultat que tindrà la persona per trobar la solució.
Per tal de construir un problema de Sudoku, cal tenir en compte que els números originals han de portar a una única solució. D'això se n'anomena un Sudoku vàlid. El constructors de problemes de Sudoku busquen també la bellesa de la figura que formen els números a les caselles, igual que també busquen una harmonia en la distribució de les xifres que es donen com a pistes. Per exemple, és molt difícil construir un problema de Sudoku de 18 xifres que sigui simètric respecte a una rotació de 180 graus. Hi ha problemes amb només 17 xifres, però no n'hi ha amb només 16 xifres. Així i tot, no s'ha pas pogut demostrar que 17 sigui el número mínim de xifres inicials que un problema pugui tenir. Pel que fa al número de xifres inicials que cal en un problema, hi ha quadrats llatins (Sudokus resolts i completats) que no poden partir de problemes amb només 17 xifres, sinó que en cal més.[10]
Els sudoku més comuns (els originals) són els de 9×9 amb regions de 3×3. Tot i això, hi ha sudoku de mides diferents, de fins a 25×25, alguns dels quals amb noms especials.
En alguns s'hi ha afegit la regla en què els nombres de les diagonals principals també han de ser únics. Hi ha variants també on algunes cel·les estant ombrejades i hi ha d'haver nombres parells. En alguns sudoku les cel·les tenen diferents colors i a més de complir-se la regla de fila, columna i regió, no hi pot haver cap nombre repetit en les cel·les del mateix color. Hi ha sudokus, com el Killer sudoku del diari The Times on certs segments han de tenir un resultat mitjançant operacions matemàtiques.
A més hi ha sudoku irregulars de diferents mides on les regions no són quadrats.
També hi ha sudoku que no tenen regions: només files i columnes. Les mides més conegudes són: 6×6, 9×9, 16×16, 25×25, 30×30, 36×36 i 49×49.
Hi ha versions que inclouen lletres en comptes de nombres, i en alguns casos aquestes lletres formen mots. També és conegut el sidoku, on es canvien els nombres per les notes musicals.
També guarda relació amb els sudoku el sudokuto, on dos jugadors van escrivint nombres en una taula fins que un aconsegueix completar una columna, fila o regió amb tots els nombres o s'equivoca en escriure'ls.
El kenken, inventat el 2004 pel professor de matemàtiques japonès Tetsuya Miyamoto, és una variant on es fa servir també el càlcul.
La primera competició mundial va tenir lloc a Lucca, Itàlia, del 10 al 12 de març del 2006. La guanyadora va ser Jana Tylova, una noia de 31 anys de la República Txeca. La competició va incloure variants del sudoku; n'hi ha una llista completa aquí PDF (anglès).
La The United States Sudoku Association Inc. és una corporació que organitza tornejos arreu dels Estats Units.