Algorisme de backtracking - Historial de revisió

Enric: /* Backtrack Sudoku recursiu */

2016-10-09T15:40:23Z

Backtrack Sudoku recursiu

2016-10-09T15:39:46Z

Backtrack Sudoku recursiu

2013-12-05T15:08:51Z

Backtrack Sudoku recursiu

2013-12-05T15:07:00Z

Backtrack Sudoku recursiu

2013-12-02T16:03:37Z

Backtrack Sudoku recursiu

2013-12-01T10:27:42Z

Intorducció

2013-12-01T10:27:12Z

2013-11-30T19:49:05Z

Exemple del Sudoku

2013-11-30T17:32:00Z

Exemple del laberint

2013-11-30T17:30:55Z

Exemple del Sudoku

@@ Línia 129: / Línia 129: @@
 funció backtrack(fila,col):
 * si és cel·la fixa
-** passa a la següent (return backtrack)
+** passa a la següent (return backtrack() <- recursió)
 * sino
 *# per tots els valors possibles de la cel·la (de 1 a 9):
 *#* si compleix regles del Sudoku:
 *#*# si hem arribat a la darrera cel·la (9,9) retornem TRUE
-*#*# provem backtrack amb la següent cel·la i si torna TRUE, tornem TRUE
+*#*# provem backtrack (recursió) amb la següent cel·la i si torna TRUE, tornem TRUE
 *#*# sino (backtrack falla) seguim
 *# sino (no ha funcionat amb cap dels valors possibles)

@@ Línia 127: / Línia 127: @@
 === Backtrack Sudoku recursiu ===
-def backtrack(fila,col):
+funció backtrack(fila,col):
-* per tots els valors possibles de la cel·la:
+* si és cel·la fixa
-*# check del nou valor
+** passa a la següent (return backtrack)
-*# si és bo o és una cel·la fixa:
+* sino
-*#* calculem següent cel·la (fila,col; si es fixa la saltem)
+*# per tots els valors possibles de la cel·la (de 1 a 9):
-*#* check si hem arribat al final (return true)
+*#* si compleix regles del Sudoku:
-*#* cridem backtrack( cel·la seguent )
+*#*# si hem arribat a la darrera cel·la (9,9) retornem TRUE
-*#* Si ens retorna OK
+*#*# provem backtrack amb la següent cel·la i si torna TRUE, tornem TRUE
-*#** retornem true
+*#*# sino (backtrack falla) seguim
-* si no es cel·la fixa: reset cel·la (=0)
+*# sino (no ha funcionat amb cap dels valors possibles)
-* retornem fals (hem provat totes les opcions possibles sense èxit)
+*#* esborra la cel·la
 <br>

@@ Línia 131: / Línia 131: @@
 *# check del nou valor
 *# si és bo o és una cel·la fixa:
-*#* calculem següent cel·la
+*#* calculem següent cel·la (fila,col; si es fixa la saltem)
 *#* check si hem arribat al final (return true)
 *#* cridem backtrack( cel·la seguent )

@@ Línia 136: / Línia 136: @@
 *#* Si ens retorna OK
 *#** retornem true
-* reset cel·la (=0)
+* si no es cel·la fixa: reset cel·la (=0)
 * retornem fals (hem provat totes les opcions possibles sense èxit)

@@ Línia 136: / Línia 136: @@
 *#* Si ens retorna OK
 *#** retornem true
 * retornem fals (hem provat totes les opcions possibles sense èxit)

@@ Línia 2: / Línia 2: @@
 <br>
-== Intorducció ==
+== Introducció ==
 El nom ''backtrack'' es sol traduir per '''tornada enrera'''. És a dir, intentem explorar totes les combinacions i quan veiem que un determinat camí no pot solucionar el problema, tornem enrera i provem la següent combinació.

@@ Línia 1: / Línia 1: @@
-El ''backtracking és una tècnica algorísmica per trobar solucions a problemes a base de provar totes les possibles solucions.
+El ''backtracking'' és una tècnica algorísmica per trobar solucions a problemes a base de provar totes les possibilitats de forma sistemàtica.
 Aplicacions típiques del ''backtracking'' son els laberints i el Sudoku.
 == Exemple del laberint ==

@@ Línia 112: / Línia 112: @@
 Suposem que tenim 2 matrius:
-* Matriu del Sudoku (amb els nombres)
+* Matriu del Sudoku (amb els nombres) de 9x9
 * Matriu de valors possibles per cada cel·la.
 <br>

← Versió més antiga		Revisió del 17:32, 30 nov 2013
Línia 26:		Línia 26:
	* v = visitada		* v = visitada

		+	<br>
		+
		+	=== Laberint recursiu ===
	L'algorisme RECURSIU que ens ho resol seria aquest.		L'algorisme RECURSIU que ens ho resol seria aquest.

← Versió més antiga		Revisió del 17:30, 30 nov 2013
Línia 106:		Línia 106:

	== Exemple del Sudoku ==		== Exemple del Sudoku ==
−	...~~ja arribarà~~...	+	Per resoldre un Sudoku es pot utiltizar un backtrack, sigui recursiu o amb pila.
		+
		+	Suposem que tenim 2 matrius:
		+	* Matriu del Sudoku (amb els nombres)
		+	* Matriu de valors possibles per cada cel·la.
		+
		+	<br>
		+
		+	=== Backtrack Sudoku recursiu ===
		+
		+	def backtrack(fila,col):
		+	* per tots els valors possibles de la cel·la:
		+	*# check del nou valor
		+	*# si és bo o és una cel·la fixa:
		+	# calculem següent cel·la
		+	# check si hem arribat al final (return true)
		+	# cridem backtrack( cel·la seguent )
		+	# Si ens retorna OK
		+	#* retornem true
		+	* retornem fals (hem provat totes les opcions possibles sense èxit)
		+
		+	<br>
		+
		+	=== Backtrack Sudoku amb pila ===
		+	...proveu vosaltres...