Sudoku en Android

Guia per desenvolupar un joc de Sudoku en Android.

Els principals objectius son:

• Conèixer la creació d'elements gràfics de forma programàtica.
• Conèixer l'element Spinner (dropdown).
• Manipular els elements gràfics.
• Aplicar el patró MVC (Model-Vista-Controlador)
• Conèixer l'algorisme de backtrack (només per a ninjas!)

Abans que res

Se suposa que coneixes les bases de Android.

Crea un nou projecte amb una EmptyActivity i puja el repo a Git.

Creant el taulell de la GUI amb Spinners

Treballarem amb TableLayout d'Android.

Com que volem fer-ho programàticament, millor mira aquest exemple comparatiu per construir TableLayout amb XML o programàticament.

Primer caldrà crear un layout general de MainActivity on posarem un TableLayout.

Segon, al onCreate de MainActivity afegim al TableLayout objectes Spinner fins formar una quadrícula de 9×9.

Mira l'article Android Spinner per veure com crear un Spinner programàticament.

Et caldrà retocar l'estil dels Spinners per tal que et càpiguen, eliminant la fletxa del dropdown:

Spinner spinner = new Spinner(this);
spinner.setBackground(null);
spinner.setPadding(5, 5, 5, 5);

Connectant les callback dels Spinner

Llegeix bé l'apartat Connectant les callback dels spinner de l'article d'Android Spinner.

Al final caldrà que d'una manera o altra, connectis els spinner a les funcions:

• onItemSelected: és on activarem la lògica del nostre joc.
• onNothingSelected: és obligatoria implementar-la, però segurament no hi posarem res de codi.

Aplicant Tags als Spinners per identificar-los

Quan rebem una crida de callback al Listener (sigui un objecte a part o una funció de la MainActivity, necessitarem identificar els Spinner.

Una forma molt còmoda és utilitzar els setTag i getTag, unes funcions genèriques de totes les Views. Podem aplicar-ho al crear l'element al onCreate:

spinner.setTag(R.id.fila,fila);
spinner.setTag(R.id.col,col);

Així, quan rebem una crida a onItemSelected sabrem quin element s'ha modificat fent:

int fila = (int) adapterView.getTag(R.id.fila);
int col = (int) adapterView.getTag(R.id.col);

Abans, perquè aquest codi funcioni, cal definir l'identificador R.id.fila i R.id.columna dins de l'arxiu values/strings.xml:

values/strings.xml

<item name="fila" type="id" />
<item name="col" type="id" />

MVC Sudoku: creant el model

Seguint el patró de disseny MVC (Model - Vista - Controlador) ja tenim la part de Vista. Ens faltarà el Model i Controlador. Aquesta part la farem implementant una class SudokuModel que pugui ser suficientment genèrica com perquè pugui reutilitzar-se en altres entorns Java (com per exemple en una aplicació desktop implementada amb Swing o JavaFX).

El core del model serà, òbviament, una matriu de int de 9×9.

Haurà de tenir, al menys, els següents mètodes:

• getVal : per obtenir una dada del model.
• setVal : per intentar canviar un número de la partida de Sudoku. Si no pot settejar-lo (el valor és incorrecte), ens retorna el valor -1 (el 0 el reservem per a la cel·la buida.
• comprovaFila : comprova que la fila indicada als paràmetres compleix les normes del Sudoku.
• comprovaCol : ídem per la columna.
• comprovaQuad : ídem pel quadrant.
• creaPartida : ens crea uns quants elements aleatoris per iniciar una partida. Aquests elements aleatoris han de complir amb les regles del Sudoku.

Millora de la implementació del model com a llibreria

Refrescant la View o GUI

A part, fora del model, necessitarem una funció per refrescar les dades de visualització de la partida al GUI. Com que no és una funció del Model, sinó que és de visualització, no ha d'estar a SudokuModel sinó que la implementarem a MainActivity.

• refrescaGUI() : traspassa les dades del model a la interfície gràfica (els Spinners).

En aquesta funció caldrà agafar totes les dades del Model i refrescar la Vista (els Spinners). Per tant, ara necessitarem tenir tots els Spinner ben localitzats en una matriu estàtica : Spinner[][]. Així serà molt fàcil accedir al Spinner adequat (fila, columna).

Init bug !

Jugar la partida i arribar al FINAL

Per poder oferir una partida al jugador caldrà que omplim algunes cel·les i les fem fixes. Això vol dir que en aquelles cel·les fixes no haurem de poder entrar valors al Spinner (es pot fer un disable).

És important acabar el joc, of course.

Solver de Sudoku amb algorisme de backtracking

Si has resolt fins aquí i ets dels més agosarats, voldràs provar de trobar solució a la partida que has generat de forma automàtica. Això es pot fer amb un clàssic algorisme de backtracking. En el fons, aquest el què fa és provar sistemàticament totes les combinacions possibles fins que troba una de vàlida, similarment al que coneixem per un «atac de força bruta».

Aquí tens una breu explicació i psuedo-codi de l'algorisme de backtrack recursiu per al Sudoku.

Check partida resoluble

Quan inicialitzem una partida aleatòriament, encara que els nombres que posem compleixin les regles del Sudoku (no repetir números en files, columnes ni quadrants) això no assegura que aquesta partida sigui resoluble.

Per assegurar-nos de que una partida és resoluble, quan la creem i abans de passar-la a l'usuari, li aplicarem el Solver que hem realitzat a l'exercici anterior, el qual ens dirà si té solució o no (i en un temps raonable, pel què ha d'estar optimitzat).

A més, les regles del Sudoku inclouen un altre requisit: que la partida no tingui vàries solucions, sinó només una de sola. Per tant, haurem de modificar el nostre solver perquè també ens determini si té més d'una solució. Si ens dona una 2a solució, tornarem a descartar la partida.