Ver la versión completa : backtracking pseudo n-reinas java
Hispasat88
08-05-2009, 19:57
Hola a todos,
Tengo que hacer una aplicacion que distribuya en un tablero de ajedrez, de 8x8, estas piezas y conseguir que no se maten entre ellas, teniendo en cuenta los movimientos que pueden realizar cada una.
2 Reinas
2 Torres
2 Caballos
2 Alfiles
El problema es muy parecido al de las n-reinas, y hay que resorverlo con backtracking en java.
Yo no tengo casi nada de idea de esta tecnica, y me gustaria que me ayudasen con tutoriales o lo que fuese, para poder implementar este algoritmo.
Muchas Garcias a todos
Hola Hispasat88
En este problema, o cualquier otro que quieras abordar con backtracking, lo principal es poder entender el problema como un arbol que debe ser recorrido.
Particularmente, aca se puede considerar cada nodo del arbol como el problema de situar una pieza en el tablero. Siendo cada hijo, cada una de las posibles posiciones en donde se puede poner la pieza.
Es decir, la raiz del arbol sera situar la primer pieza en el tablero, suponiendo que el tablero es cuadrado de lado n, habran nxn hijos para cualquier nodo.
Los nodos inmediatos por debajo de la raiz se corresponderan con el problema de poner la segunda pieza en el tablero, y se continuara de esta forma hasta que ya no queden piezas que colocar.
Una vez que tenes esto, el backtracking consiste en recorrer este arbol con bsf (busqueda en profundidad).
Un esquema podria ser el siguiente:
BT(i)
IF i=cantidad de piezas THEN
FOR EACH casilla en tablero DO
IF libre(casilla) THEN
mostrarSolucion()FI
OD
ELSE
FOR EACH casilla en tablero DO
IF libre(casilla) THEN
marcartablero(casilla,LPIEZAS(i))
BT(i+1)
desmarcartablero(casilla,LPIEZAS(i))
FIODFI
Como veras, este es hacer bruteforce. El algoritmo puede ser ampliamente mejorado, pero es para que te hagas una idea de en que consiste el backtracking.
Si tengo algo de tiempo te pongo algo de codigo en c, no es java pero se parece bastante.
Saludos
Una vez que tenes esto, el backtracking consiste en recorrer este arbol con bsf (busqueda en profundidad).
Bueno las siglas de búsqueda en profundidad son DFS (Deep First Search) :D
BFS (Breadth First Search) es búsqueda en anchura, otra forma de recorrer un árbol.
Por lo demás, tienes dos opciones:
1º Utilizar una función y meter allí todo el código (con llamadas recursivas?) tirando líneas de código como un estresado y volverte loco con el algoritmo... haciendo trazas, recibiendo errores, etc... o bien
2º Modularizar como diré a continuación.
Diré como recomendación que lo mejor es utilizar patrones de diseño. En concreto, para este caso utilizaría el patrón plantilla (Template Method) (http://es.wikipedia.org/wiki/Template_Method_(patr%C3%B3n_de_dise%C3%B1o)).
Debes tener claro qué es lo que pretendes conseguir, ya que el backtracking ofrece 3 posibilidades:
1º Obtener una solución
2º Obtener todas las soluciones posibles
3º Obtener la mejor solución.
Para este problema la 3ª opción no es de importancia ya que todas las soluciones posibles son iguales de buenas.
Un saludo.
Si la pifie mal, DFS es el acronimo correcto para busquda en profundidad.
Gracias por la correccion hystd
Saludos
Hispasat88
14-05-2009, 21:56
Ok, entendido, muchas gracias. En cuanto tenga el codigo listo lo subo. aunque no sea muy bueno pero me gusta compartir el codigo por si alguna vez a alguien le puede ayudar.
de nuevo muchas gracias