| MARCAR EL NÚMERO | ||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| DESMARCAR | ||||||||
En el nostre Sudoku, el podem col·locar, en color verd, a la casella (B, 9) dins el bloc B3 (imatge de l'esquerra).
Repetim de manera recursiva el mateix algorisme amb tots els dígits de l’1 al 9 omplint totes les caselles possibles. Comencem amb el número 3 (imatge central), quedant col·locats ja els 9 tresos possibles, un a cada bloc (B1 a B9), sense repetir-ne cap en cap fila ni columna.
Continuem aplicant el mateix algorisme de manera recursiva amb tots els números restants fins arribar a la resolució complerta del Sudoku (imatge de la dreta).
Malauradament, no sempre un Sudoku serà tant senzill de resoldre i s’haurà de pensar una mica més i aplicar nous algorismes de resolució.
Les tres condicions que s’han d’acomplir per tal de que el número col·locat en una casella són: 1) el número no s’ha de repetir en la seva columna; 2) el número no s’ha de repetir en la seva fila; 3) el número no s’ha de repetir en el seu bloc.
Per tant un mètode per esbrinar quin és aquest número únic seria considerar tres conjunts B, F, C amb:
Aleshores, si B ꓵ F ꓵ C = { n } → n és el número buscat. L’únic número que és absent a fila, columna i bloc.
La lògica del deep filler és senzilla: donada una fila/columna/bloc, si observem que un número es pot col·locar en una única de les seves aquest és el número correcte. La part complicada és arribar a observar-ho.
Observem ara el Sudoku de l'esquerra, on el 3 de la casella (D, 3) s’ha col·locat aplicant el mètode anterior (basic filler):
Ens fixem ara en la casella (D, 1) i apliquem el nou mètode del deep filler seguint la seva columna i fixant-nos en cada cas en quins són els únics números que no són ja col·locats ni en el bloc, ni en la fila, ni en la columna:
Al conjunt de (D,1) hi trobem el número 4, que no és present a cap dels altres conjunts. Aquest és doncs el número a col·locar a (D, 4) (imatge de la dreta).
Continuem omplint el nostre Sudoku i arribem a la posició següent, fixant-nos en la casella (A, 3), la primera de les caselles buides del bloc que en té menys per omplir. És a dir, una casella amb el menor nombre de solucions possibles. En aquest cas { 1, 6 }.
Seleccionem, a l’atzar, el número 6 com a possible solució. Continuem resolent el Sudoku i arribem finalment a la posició de la imatge del mig. Observem que a la casella (G, 6) únicament es pot col·locar el número 8, que ja és col·locat al seu bloc. Per tant tirem enrere (backtracking) i col·loquem a la casella (A, 3 ) el número correcte, l’1, a la casella (C, 3) el 6, i continuem resolent el Sudoku (imatge de la dreta).
Informàticament el procés de backtracking cerca en profunditat en un arbre de possibles solucions, on cada node representa una decisió i cada branca representa una opció. El següent exemple és tret de la wikipedia.
L’algorisme torna enrere al arribar dins la branca actual a un carreró sense sortida. Aleshores es desplaça al node anterior i n’explora les seves branques. És un mètode de resolució per força bruta que consumeix exponencialment el temps de procés al augmentar la dimensió del Sudoku.
Combinant backtracking, basic filler i deep filler s’aconsegueix reduir notablement el temps de procés. A Alexarr6/sudoku-solver de Github trobareu una implementació del solucionador de sudokus en llenguatge python.
Jordi Coll Vera - 2024