Sudoku

Jo pensava que el sudoku era un d’aquests jocs mil·lenaris japonesos que havia exercitat la ment de monjos i Shoguns per a poder arribar a tota classe de revelacions pròpies del senyor Miyagi i que el deixen a un bocabadat durant una bona estona.

Però resulta que de joc mil·lenari i japonès en té ben poc, ja que va ser l’arquitecte nord-americà Howard Garns, qui l’inventà… en 1979! Quina decepció.

Els sudokus es feren populars a Japó en la dècada dels vuitanta quan una companyia de puzzles comença a comercialitzar-los en el país de l’orient, però s’estengueren mundialment l’any 2004 quan el periòdic britànic The Times començà a incloure’ls entre les seves pàgines junt a sopes de lletres, encreuats i demés passatemps.

El joc

El joc consisteix senzillament en omplir un tauler de costats 9×9 amb nombres de l’1 al 9 de manera que no hi haja dos nombre iguals en cap fila, ni cap columna, ni cap bloc de 3×3. Els taulers de sudoku tenen la següent forma.

Sudoku

Un exemple de Sudoku (punxa per veure la solució)

Depenent del nombre de quadres plens que ens donen i la posició dels nombres amb els que comencem el joc resulta més difícil o menys.

El principi

Jo fins fa dos anys no havia jugat en ma vida al joc aquest. N’havia vist, sí, però no havia jugat mai. Fou a juny de 2007, de camí a València per comprar els bitllets del (fallit) Interrail quan vaig jugar per primera vegada amb Marina i Blai. Marina i jo ens vàrem picar a veure qui podia completar-ne més ràpidament així que em vaig comprar un llibre d’aquests que estan tot plens de sudokus per anar fent-lo durant el viatge, però circumstàncies de la vida que ja coneixeu feren que el llibre l’emplenés en l’hospital.

I a què ve tot açò? Doncs l’altre dia estàvem en classe d’Estructures de Dades i Algorismes (a.k.a EDA) aprenent sobre Backtracking i sorgí l’exemple del sudoku, així que el professor va fer un programa que resolia sudokus fent servir aquest esquema algorísmic. Quan va acabar el programa va dir: “Podríem fer que ens imprimira tots els sudokus possibles…” i va llançar el programa per a que fera això, però com que ja era hora d’acabar la classe ací va quedar la cosa.

Jo, ahir que no sabia que fer (ara que ja s’ha acabat el concurs de l’assignatura) i com que no havia practicat encara res de Backtraking per compte propi em vaig dir: “Xe, anem a fer el programeta per resoldre sudokus“. I em vaig posar en això. Quan vaig acabar-lo em vaig preguntar per què no acabar la tasca que el professor havia començat però havia abandonat per falta de temps i vaig llançar el meu programa per a que em mostrara tots els sudokus que es podien formar en un tauler de 9×9.

Ignorant de mi. Com veia que tardava me’n vaig anar a berenar esperant que quan tornes tindria ja tots els sudokus possibles. Però com ja imaginareu, quan vaig tornar el portàtil estava a 74ºC  (i això que havia limitat la freqüència a 996MHz) i el fitxer de solucions ja ocupava centenars de MB. Va ser ací quan em vaig adonar que segurament serien MOLTS sudokus

Concretament, hi han 6,670,903,752,021,072,936,960 taulers de sudoku possibles (o deixe expressat així i no en notació científica per a que s’aprecie millor la magnitud d’aquest nombre). I ací és on comença el friquisme.

Parlant matemàticament…

Hi ha un extens article en la Wikipedia anglesa dedicat a les matemàtiques relacionades amb aquest joc, la seva llista de referències no es queda curta i són moltes les investigacions sobre Combinatòria i també Complexitat Computacional que es centren en aquest joc.

El problema general del sudoku entès com un tauler de N^2 \times N^2 caselles agrupades en blocs de N \times N (9×9 caselles agrupades en blocs de 3×3, en el nostre cas), es pot expressar com un problema de colorejat d’un graf, on cada casella seria un vèrtex del graf enumerat de la forma (x,y) (on x, y \in \mathbb{N} \mid x \le N^2 \wedge y \le N^2)¹ i on dos vèrtex i, j estarien units per una aresta si:

  • x_i = x_j (dues caselles d’una mateixa columna).
  • y_i = y_j (dues caselles d’una mateixa fila).
  • \lceil \frac{x_i}{N} \rceil = \lceil \frac{x_j}{N} \rceil \wedge \lceil \frac{y_i}{N} \rceil = \lceil \frac{y_j}{N}\rceil (dues caselles en un mateix bloc).

Llavors, la solució seria assignar un color entre els N^2 possibles a cada vèrtex (un nombre de l’1 al 9 vaja) de manera que qualsevol aresta no tinga el mateix color en el seus dos extrems.

Doncs veges tu per on, aquest problema és un problema del tipus NP-Complet. Jo havia sentit parlar d’aquesta classe de problemes (per tot allò de P = NP?, un dels set problemes del mil·leni, la solució dels quals és premiada amb un milió de dòlars), però fins aquesta vesprada no sabia concretament que era un problema NP-Complet i tampoc estic segur de saber-ho ara, així que abans de contar-vos alguna bajanada us referencie a l’article de la Wikipedia.

El que sí us sé dir és que, en poques a paraules, no es coneix un algorisme “eficient”, on eficient significa polinòmic (O(n^k) \mid k \in \mathbb{N}) per solucionar el problema. El que fa l’algorisme basat en Backtracking és explorar tot l’arbre de possibles solucions descartant aquelles que no complisquen les condicions del joc (descrites anteriorment).

Haurem de renunciar doncs, de moment, a trobar tots els possibles sudokus… Podríem seguir parlant de com, almenys, comptar quantes són aquestes solucions, però per això necessitaríem un apunt encara més llar i ja s’està fent tard i tampoc era eixe l’objectiu del post. Si us he despertat un poc l’interès i us ha picat el cuquet friqui, podeu visitar aquesta pàgina web de Bertram Felgenhauer i Frazer Jarvis que dugueren endavant els càlculs.

¹ Pregue que disculpeu el formalisme d’algunes expressions, però aprofite l’apunt per provar que dóna de sí el plugin WP-Latex.

Aquesta entrada s'ha publicat en Curiositats, Informàtica, Matemàtiques, Programació i etiquetada amb , , , , , , , , , , , . Afegiu a les adreces d'interès l'enllaç permanent.

4 comentaris a l'entrada: Sudoku

  1. Vinz diu:

    Ja posats a fer el friki, porte uns mesos viciat als Sidokus, són una variant del sudoku però musical: http://www.sidokus.com/
    Tan sols fa falta saber-te les notes de la escala musical i prou. El més divertit és que les caselles rosa o colorejades, et plantegen una incògnita més divertida, que és un tema musical, i per a contestar aquesta si que has de tenir cultura musical.

    Fer un programa que ens torne l’arbre de solucions és molt semblant però les restriccions són un poc putes perquè els quadres tonals no són simètrics i semblen més bé el joc del tetris. Tot açò és perquè amb 7 notes musicals tens 7 caselles que no pots fer un quadre perfecte.

    També és interessant programar un arbre de solucions per a intentar esbrinar el tema musical mitjançant combinatòria.

    Si algú s’anima que m’avise xD

  2. Warning diu:

    “The Clay Mathematics Institute is offering a $1 million reward to anyone who has a formal proof that P=NP or that P≠NP.”

    Vaja doncs lo del milio de dolars pareix ser veritat!!. Estan molts segurs de la seva complexitat.

    Impresionant la quantitat de calculs i situacions que poden tindre aquestos quadriculats que ixen als diaris.

  3. Joan diu:

    Afegir que únicament 1 dels 7 problemes del mil·leni han estat resolts: el de la conjectura de Poncairé que fou resolt al 2002 pel matemàtic rus Grigori Perelman (bo, hi ha certa polèmica ací) qui renuncià a la Medalla Fields (alguna cosa així com un Nobel però per als matemàtics) i al premi que acompanya aquesta medalla. Les seva justificació per a la renúncia era que: “si la demostració era correcta no hi havia possibilitat de major reconeixement” i que “el tribunal no estava qualificat per avaluar-lo”… Tot un personatge.
    http://es.wikipedia.org/wiki/Conjetura_de_Poincar%C3%A9
    http://es.wikipedia.org/wiki/Grigori_Perelmán

  4. Joan diu:

    Per cert… [Warning] m’ha recordat que és el post amb id 666!!! XD

Deixa un comentari

L'adreça electrònica no es publicarà Els camps necessaris estan marcats amb *

Podeu fer servir aquestes etiquetes i atributs HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>