Sudoku
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]
 | |
| Tipus | joc d'habilitat mental i esport mental  |
|---|---|
| Basat en | Quadrat llatí |
| Gènere | joc d'habilitat mental |
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]
Orígens
modificaEl 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.
Normes
modifica
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.
Mètodes de resolució
modificaL'estratègia per a resoldre un trencaclosca es pot considerar com la combinació de tres processos: escanerització, marcatge i anàlisi.
Escanerització
modificaL'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.
- Trama creuada: es tracta de l'escanerització de files (o columnes) per a identificar quina línia en una regió particular pot contenir un nombre determinat mitjançant un procés d'eliminació. Aquest procés es repeteix amb les columnes (o files). Per obtenir resultats més ràpids, els nombres són escanejats de forma ordenada, segons la seva freqüència d'aparició. És important realitzar aquest procés sistemàticament, comprovant tots els dígits de l'1 al 9.
- Recompte de l'1 al 9 per regions, files i columnes per identificar nombres perduts: el recompte basat en l'últim nombre descobert pot augmentar la velocitat de la recerca. També pot ser el cas (és típic en trencaclosques més difícils) que el valor d'una cel·la individual pugui ser determinat mitjançant un recompte invers, això és, escanejant la seva regió, fila o columna per a valors que no poden ser, per a veure quin és el que hi falta.
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ó.
Marcatge
modificaL'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ó.
Anàlisi
modificaHi ha dues aproximacions principals: eliminació i "i-si".
- En eliminació, el progrés es realitza mitjançant la successiva eliminació de nombres candidats per a una o més cel·les, fins a deixar només una elecció. Després d'assolir cada resposta, cal fer una nova escanerització (habitualment comprovant l'efecte de l'últim nombre). Hi ha una sèrie de tàctiques d'eliminació. Una de les més comunes és l'esborrament "del candidat no coincident". Les cel·les amb idèntica configuració de nombres candidats es diu que coincideixen si la quantitat de nombres candidats en cadascuna és igual al nombre de cel·les que els contenen. Per exemple, es diu que cel·les coincideixen amb una particular fila, columna o regió si dues cel·les contenen el mateix parell de nombres candidats (p,q) i no altres, o si tres cel·les contenen el mateix triplet de nombres candidats (p,q,r) i no altres. Aquestes són, essencialment, contingències coincidents. Aquests nombres (p,q,r) que apareixen com a candidats en qualsevol lloc en la mateixa fila, columna o regió en cel·les no coincidents, poden ser esborrats.
- En l'aproximació "i-si", se selecciona una cel·la amb només dos nombres candidats i es realitza una conjectura. Les etapes de dalt es repeteixen llevat que es trobi una duplicació; en aquest cas, el candidat alternatiu és la solució. En termes lògics aquest mètode es coneix com a reducció a l'absurd. "Nishio" és una forma limitada d'aquesta aproximació: per a cada candidat per a una cel·la, la qüestió que es planteja: entrarà un nombre particular d'una configuració en un altre emplaçament? Si la resposta és sí, aleshores aquest candidat pot ser eliminat. L'aproximació "i-si" requereix un llapis i una goma. Aquesta aproximació pot ser desaprovada per puristes lògics per massa assaig i error però pot arribar a solucions de forma clara i ràpida.
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.
Resolució per ramificació i poda
modificaEl mètode de ramificació i poda permet resoldre el trencaclosques amb una sèrie d'algorismes.[9]
Resolució mitjançant ordinadors
modificaPer 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ó.
Construcció
modificaPer 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]
Variants
modifica
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.
Competicions
modificaLa 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.
Referències
modifica- ↑ Grossman, Lev. «The Answer Men». Time, 11-03-2013. Arxivat de l'original el 1 març 2013. [Consulta: 4 març 2013]. Arxivat August 16, 2013[Date mismatch], a Wayback Machine.
- ↑ Lawler, E. L.. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. West Sussex: John Wiley & Sons, 1985. ISBN 0-471-90413-9.
- ↑ Arnoldy, Ben «Sudoku Strategies». The Christian Science Monitor.
- ↑ Schaschek, Sarah «Sudoku champ's surprise victory». The Prague Post, 22-03-2006 [Consulta: 18 febrer 2009]. «Còpia arxivada». Arxivat de l'original el d’agost 13, 2006. [Consulta: d’agost 23, 2021].
- ↑ Smith, David «So you thought Sudoku came from the Land of the Rising Sun ...». The Observer, 15-05-2005 [Consulta: 13 juny 2008]. «The puzzle gripping the nation actually began at a small New York magazine»
- ↑ Devlin, Keith «The Numbers Game (book review of Taking Sudoku Seriously by Jason Rosenhouse et al.)». The Wall Street Journal [Weekend Edition], January 28–29, 2012, p. C5.
- ↑ Hayes, Brian «Unwed Numbers». American Scientist, 94, 1, 2006, pàg. 12–15. DOI: 10.1511/2006.57.3475.
- ↑ Callarissa, Joan «Mor l'editor Maki Kaji, considerat el “padrí dels sudokus”». Diari ARA, 18-08-2021, pàg. A la fresca, 3.
- ↑ Martí, Narciso; Verdejo, Alberto; Ortega Yolanda. Estructuras de datos y métodos algorítmicos: ejercicios resueltos (en castellà). Madrid: Prentice Hall, 2003.
- ↑ Rosenhouse, Jason. Taking sudoku seriously : the math behind the world's most popular pencil puzzle. Oxford: Oxford University Press, 2011. ISBN 978-0-19-992108-9.
Enllaços externs
modifica