The Blog

Algoritmo Backtracking - NReinas

2017-06-18 13:00:00

Backtracking es una manera de recorrer un arbol de posibles soluciones. Imagina que quieres cruzar un laberinto, el laberinto tiene una puerta de entrada y salida.

Estas frente a la puerta de entrada y tienes tres caminos a seguir, escoges el de la derecha y marcas con una raya en la pared antes de entrar en ese camino, caminas y te topas con otras division, nuevamente tres caminos, escoges el de la derecha y lo marcas (en la pared con una raya de tiza), te vas por el camino y te encuentras que esta cerrado..
¿Que haces? pues te devuelves (back) y vuelves a la ultima division ahora tienes solo dos caminos para escoger, escoges el de mas a la derecha y que no esta marcado, lo marcas, y avanzas, cerrado, te devuelves a la division, escoges el de mas a la derecha que no este marcado (igual queda uno) lo marcas, avanzas, cerrado, te devuelves, y.. no queda nada para escoger, todo esta marcado, te devuelves y vuelves a la primera division, y escoges el camino mas a la derecha que no este marcado...

Funcionamiento BackTracking:


Enunciado:
Colocar N reinas en un tablero rectangular de dimensiones N por N de forma que no se encuentren más de una en la misma línea: horizontal,vertical o diagonal.

Test:

public class Test {

    public static void main(String[] args){

    	List> b = new BackTracking().recursividad(0,new ArrayList(),new TreeSet(),new TreeSet(),
        												      new ArrayList>(),4);
        System.out.println("Soluciones: "+b.size());
        for(List c : b){
			System.out.println(c);
        }

    }
}

BackTracking:
public class BackTracking {

    public List> recursividad(Integer x,List yOcupadas,Set diagonalesPrincipalesOcupadas,Set diagonalesSecundariasOcupadas,
    									  List> resultado,Integer reinas){

    	if(x == reinas){

			//Posibles soluciones
			List lista = new ArrayList(); //Creo una lista con las posiciones actuales
			for(int i=0;i<.reinas;i++){
				lista.add(new Reina(i, yOcupadas.get(i)));
			}
			if(getNumeroDeConflictos(lista,reinas) == 0){ //Compruebo si esa lista es valida
				Integer i = 0;
				if(!resultado.containsAll(lista)){ //Si no esta en la solucion la lista, la añado
					resultado.add(i, lista);
					i++;
				}
			}
 
    	}else{
			for(Integer a : getAlternativa(x,yOcupadas,diagonalesPrincipalesOcupadas,diagonalesSecundariasOcupadas,reinas)){ //Las alternativas
			
				yOcupadas.add(a);
				calculaPropiedadesDerivadas(yOcupadas,diagonalesPrincipalesOcupadas,diagonalesSecundariasOcupadas);
			
			    recursividad(x+1, yOcupadas,diagonalesPrincipalesOcupadas,diagonalesSecundariasOcupadas,resultado,reinas);
			
				yOcupadas.remove(yOcupadas.size()-1);
				calculaPropiedadesDerivadas(yOcupadas,diagonalesPrincipalesOcupadas,diagonalesSecundariasOcupadas);
			}
    	}
        return resultado;

    }
    
	private void calculaPropiedadesDerivadas(List yOcupadas,Set diagonalesPrincipalesOcupadas,Set diagonalesSecundariasOcupadas){
		diagonalesPrincipalesOcupadas = new HashSet<>();
		diagonalesSecundariasOcupadas = new HashSet<>();
		for(int x=0; x < yOcupadas.size();x++){
			diagonalesPrincipalesOcupadas.add(yOcupadas.get(x)-x);
			diagonalesSecundariasOcupadas.add(yOcupadas.get(x)+x);
		}
	}

    public List getAlternativa(Integer x,List yOcupadas,Set diagonalesPrincipalesOcupadas,Set diagonalesSecundariasOcupadas,Integer reinas){
		Stream s = IntStream
				.range(0, reinas)
				.filter(y -> !yOcupadas.contains(y)
						&& !diagonalesPrincipalesOcupadas.contains(y-x)
						&& !diagonalesSecundariasOcupadas.contains(y+x)
						)
				.boxed();
		return s.collect(Collectors.toList());
    }
    
	public Integer getNumeroDeConflictos(List ls,Integer reinas){
		Set diagonalesPrincipalesOcupadas = new HashSet<>();
		Set diagonalesSecundariasOcupadas = new HashSet<>();
		for(Reina r:ls){
			diagonalesPrincipalesOcupadas.add(r.getY()-r.getX());
			diagonalesSecundariasOcupadas.add(r.getY()+r.getX());
		}
		return 2*reinas 
				- diagonalesPrincipalesOcupadas.size()
				-diagonalesSecundariasOcupadas.size();
	}

}

Reinas:
public class Reina {
	private Integer y;
	private Integer x;
	
	public Reina(int x, int y) {		
		this.x = x;
		this.y = y;
	}
	
	public Integer getY() {
		return y;
	}
	public Integer getX() {
		return x;
	}

	public Integer getDiagonalPrincipal(){
		return y-x;
	}
	public Integer getDiagonalSecundaria(){
		return y+x;
	}
	
	@Override
	public String toString() {
		return "[" + x + ","+ y + "]";
	}
	
}

Resultado obtenido:
[[0,2], [1,0], [2,3], [3,1]]
[[0,1], [1,3], [2,0], [3,2]]

Comments (0)

  • ¡Se el primero en comentar!

Leave a comment

Su mensaje ha sido enviado correctamente. ¡Muchas gracias!. Recuerda reiniciar la pagina para ver el comentario.

No ha sido posible enviar el mensaje. Revise los datos