====== Sudoku en Android ======

Guia per desenvolupar un joc de Sudoku en [[Android]].

{{ https://upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Sudoku_Puzzle_by_L2G-20050714_standardized_layout.svg/1024px-Sudoku_Puzzle_by_L2G-20050714_standardized_layout.svg.png?250 }}


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!)


{{tag> #Dam #DamMp08 #DamMp08Uf01 Android mobile java }}


===== 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 [[https://developer.android.com/guide/topics/ui/layout/grid?hl=es-419|TableLayout]] d'Android.

Com que volem fer-ho programàticament, millor mira aquest [[http://justsimpleinfo.blogspot.com/2014/05/android-tablelayout-example.html|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 9x9.

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//:
<code java>
Spinner spinner = new Spinner(this);
spinner.setBackground(null);
spinner.setPadding(5, 5, 5, 5);
</code>

<WRAP todo>
Crea el taulell del Sudoku (9x9 cel·les) amb [[Android Spinner]] amb nombres fixes de l'1 al 9 mes un valor buit per deixar la cel·la sense omplir.

Crea un espai diferenciat per separar els quadrants de 3x3. Pots intentar jugar amb els //paddings// (més senzill) o bé intentar pintar la quadrícula.
</WRAP>

\\

===== Connectant les callback dels Spinner =====

Llegeix bé l'apartat [[https://bytes.cat/android_spinner#connectant_les_callback_dels_spinner|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.

<WRAP todo>
Implementa les //callback// necessàries fent que quan es canvii el valor d'un ''Spinner'' ens mostri un ''Log'' indicant-nos el text "Spinner modificat".
</WRAP>

\\

===== 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 [[https://developer.android.com/reference/android/view/View#getTag()|setTag i getTag, unes funcions genèriques de totes les Views]]. Podem aplicar-ho al crear l'element al ''onCreate'':

<code java>
spinner.setTag(R.id.fila,fila);
spinner.setTag(R.id.col,col);
</code>

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

<code java>
int fila = (int) adapterView.getTag(R.id.fila);
int col = (int) adapterView.getTag(R.id.col);
</code>

Abans, perquè aquest codi funcioni, cal definir l'identificador ''R.id.fila'' i ''R.id.columna'' dins de l'**arxiu ''values/strings.xml''**:
<file xml values/strings.xml>
<item name="fila" type="id" />
<item name="col" type="id" />
</file>

<WRAP todo>
Implementa aquests mecanismes i fen que quan es modifiqui el valor d'algun ''Spinner'' aparegui un ''Toast'' informant-nos identificant el item (fila, columna) i el seu nou valor.
</WRAP>

\\

===== 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 9x9.

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.

<WRAP todo>
Implementa el model per al Sudoku com s'ha descrit.
</WRAP>

==== Millora de la implementació del model com a llibreria ====
<WRAP info>
Pot ser interessant implementar el model en un //Java package// independent, i en un repositori independent, si volem reutilitzar el codi en altres projectes. Per exemple, podríem tenir el model de Sudoku i reutilitzar-lo en una App Android i també en una aplicació //desktop// implementada amb Swing. Per insertar un projecte dins d'un altre amb git convé utilitzar [[https://bytes.cat/git#git_submodules|Git Submodules]].

Seguint en aquesta línia, **pots treballar el model de Sudoku en un altre IDE com Eclipse o IntelliJ**, i quan tinguis el //package// funcionant, l'exportes com a JAR file dins la carpeta ''app/libs'' del projecte Android. Així podràs utilitzar la llibreria que has creat dins el projecte Android.
</WRAP>

\\

===== 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).

<WRAP todo>
Implementa el model de Sudoku en un classe nova amb els mètodes descrits.

Implementa el mètode creaPartida amb una formula senzilla, com per exemple posar números de l'1 al 9 (només 1 de cada) aleatòriament o, si vols, un en cada fila. Després ja aniràs sofisticant la creació de partida.

Comprova que si creem una partida el mètode ''refrescaGUI()'' funciona mostrant-la en els Spinners.
</WRAP>

\\

===== Init bug ! =====
<WRAP alert>
Quan s'inicialitzen els ''Spinner'' programàticament se'ns dispararà la funció de //callback// ''onItemSelected''. És el què es coneix per **//init bug//**.

Cal fer un arreglo que eviti aquest efecte, ja que en aquest inici la //callback// es cridarà... 81 cops! I Això farà anar molt lent el dispositiu i fins i tot el pot penjar (sobretot si hi hem posat un ''Toast'').

</WRAP>


<WRAP tip>
Aquí teniu una [[https://stackoverflow.com/questions/16447858/how-to-set-spinner-item-without-onitemselected-getting-called|solució per a l'init bug utilitzant Tags]], com ja hem fet abans.
</WRAP>

\\



===== 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.

<WRAP todo>
Implementa els canvis necessaris (atributs i mètodes) al ''SudokuModel'' i a les ''Views'' per poder disposar de **cel·les fixes** (un nombre predeterminat de cel·les amb valors aleatoris) a l'inici de la partida.

Quan totes les cel·les estiguin plenes i alhora compleixin les regles del Sudoku, donarem per finalitzada la partida i traurem un ''Dialog'' per felicitar l'usuari.
</WRAP>

\\

===== Solver de Sudoku amb algorisme de backtracking =====

<WRAP important>
Secció només per a les més agosarades!
</WRAP>

{{ https://markfisherfitness.com/wp-content/uploads/2013/08/ninjachallenge_zps4011c7ff.png?200 }}

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".

[[https://cacauet.org/wiki/index.php/Algorisme_de_backtracking|Aquí tens una breu explicació i psuedo-codi de l'algorisme de backtrack recursiu per al Sudoku]].

{{ https://helloacm.com/wp-content/uploads/2020/08/sudoku-solver.jpg?400 }}

<WRAP info>
Hi ha moltes tècniques de resolució de sudokus com joc (X-wing, Y-wing, etc). Aquestes són "fàcils" d'utilitzar per persones, però no son fàcils d'implementar en un programa.

En canvi, el //backtrack// seria una tècnica molt difícil que segueixi una persona, però més fàcil d'implementar en un programa. No és un algorisme òptim, en el sentit en què triga molt i consumeix CPU i memòria, però funciona.

Una optimització senzilla del //backtrack// que pot disminuir molt el temps de computació seria disposar d'una matriu extra on posaríem els valors vàlids per a cada cel·la, descartant valors impossibles (els que hi hagi a la fila, columna i quadrant de la cel·la). Llavors el bucle que fem pels possibles valors de la cel·la dins el//backtrack// es redueix i el temps de càlcul es redueix considerablement.
</WRAP>

<WRAP todo>
  - Implementar el //backtrack// del Sudoku en el model i testejar-ho amb test unitari.
  - Posar un botó "Resol" en la app, que llanci el //backtrack// en un [[Android Threads]] secundari (com en el de comunicacions) i que quan acabi, refresqui la //view// amb el mètode implementat abans.
</WRAP>

\\

===== 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.

<WRAP todo>
Crea una partida i, abans de passar-la a l'usuari, comprova que té només 1 possible solució, fent ús del solver.
</WRAP>