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ó

--- sudoku_php [2022/10/07 13:52]
enrique_mieza_sanchez [Iteració 3: jugar partida]
+++ sudoku_php [2022/10/17 18:41] (actual)
enrique_mieza_sanchez [Iteració 4: solver]
@@ Línia 49: / Línia 49: @@
 \\
-===== Iteració 4: solver =====
+===== Iteració 4: solver amb backtrack =====
+<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 un [[https://cacauet.org/wiki/index.php/Algorisme_de_backtracking|solver per al Sudoku seguint l'algorisme de backtrack]].
+Implementar el //backtrack// del Sudoku.
-Optimitzacions.
+Fes-ho en una pàgina específica, per exemple ''solver.php'', on pots agafar la partida emmagatzemada a la variable de sessió i resoldre-la.
 </WRAP>

bytes.cat

Eines de l'usuari

Eines del lloc

Diferències

Eines de la pàgina