Resultados 1 al 5 de 5

Tema: backtracking pseudo n-reinas java

  1. #1 backtracking pseudo n-reinas java 
    Iniciado
    Fecha de ingreso
    Apr 2009
    Mensajes
    13
    Descargas
    1
    Uploads
    0
    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
    ---------------
    Hispasat88
    Citar  
     

  2. #2  
    Moderador HH
    Fecha de ingreso
    Sep 2003
    Mensajes
    1.384
    Descargas
    21
    Uploads
    5
    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:

    Código:
    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))
    FI
    OD
    FI

    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
    - Me desagrada
    - ¿Por qué?
    - No estoy a su altura.
    ¿Ha respondido así alguna vez un hombre?

    Friedrich Nietzsche



    Citar  
     

  3. #3  
    Moderador Global Avatar de hystd
    Fecha de ingreso
    Jul 2005
    Ubicación
    1, 11, 21, 1211...
    Mensajes
    1.596
    Descargas
    58
    Uploads
    0
    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)
    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).

    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.
    El optimista tiene ideas, el pesimista... excusas

    Citar  
     

  4. #4  
    Moderador HH
    Fecha de ingreso
    Sep 2003
    Mensajes
    1.384
    Descargas
    21
    Uploads
    5
    Si la pifie mal, DFS es el acronimo correcto para busquda en profundidad.

    Gracias por la correccion hystd


    Saludos
    - Me desagrada
    - ¿Por qué?
    - No estoy a su altura.
    ¿Ha respondido así alguna vez un hombre?

    Friedrich Nietzsche



    Citar  
     

  5. #5  
    Iniciado
    Fecha de ingreso
    Apr 2009
    Mensajes
    13
    Descargas
    1
    Uploads
    0
    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
    ---------------
    Hispasat88
    Citar  
     

Temas similares

  1. IDE Java 3D
    Por eduk15 en el foro GENERAL
    Respuestas: 1
    Último mensaje: 10-06-2009, 14:34
  2. java
    Por rat en el foro PROGRAMACION DESKTOP
    Respuestas: 4
    Último mensaje: 07-09-2006, 19:44
  3. Java
    Por Dragoon en el foro PROGRAMACION WEB
    Respuestas: 2
    Último mensaje: 04-07-2006, 05:14
  4. [Java]
    Por clarinetista en el foro PROGRAMACION DESKTOP
    Respuestas: 0
    Último mensaje: 15-04-2004, 00:47
  5. Java
    Por clarinetista en el foro APLICACIONES
    Respuestas: 2
    Último mensaje: 07-02-2004, 16:34

Marcadores

Marcadores

Permisos de publicación

  • No puedes crear nuevos temas
  • No puedes responder temas
  • No puedes subir archivos adjuntos
  • No puedes editar tus mensajes
  •