Diferències

Ací es mostren les diferències entre la revisió seleccionada i la versió actual de la pàgina.

Enllaç a la visualització de la comparació

--- android_sudoku [2022/10/17 17:29]
enrique_mieza_sanchez [Solver de Sudoku amb algorisme de backtracking]
+++ android_sudoku [2022/10/24 13:19] (actual)
enrique_mieza_sanchez [Final de partida]
@@ Línia 1: / Línia 1: @@
 ====== Sudoku en Android ======
-Guia per fer un joc de 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:
@@ Línia 8: / Línia 11: @@
   * Manipular els elements gràfics.
   * Aplicar el patró MVC (Model-Vista-Controlador)
+  * Conèixer l'algorisme de //backtrack// (només per a ninjas!)
@@ Línia 149: / Línia 153: @@
-===== Final de partida =====
+===== Jugar la partida i arribar al FINAL =====
-És important acabar el joc. 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.
+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>
 \\
@@ Línia 156: / Línia 168: @@
 ===== 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 cercar totes les combinacions possibles fins que troba una de vàlida, similarment al que coneixem per un "atac de força bruta".
+<WRAP important>
+Secció només per a les més agosarades!
+</WRAP>
-[[https://cacauet.org/wiki/index.php/Algorisme_de_backtracking|Aquí tens una breu explicació i psuedo-codi de l'algorisme de backtrack recursiu]].
+{{ https://markfisherfitness.com/wp-content/uploads/2013/08/ninjachallenge_zps4011c7ff.png?200 }}
-Recomanació:
+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>

bytes.cat

Eines de l'usuari

Eines del lloc

Diferències

Eines de la pàgina