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.
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 
caselles agrupades en blocs de 
(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 
(on 
)¹ i on dos vèrtex 
estarien units per una aresta si:
(dues caselles d’una mateixa columna).
(dues caselles d’una mateixa fila).
(dues caselles en un mateix bloc).
Llavors, la solució seria assignar un color entre els 
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 (
) 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.
