8-puzzle(quebra cabecas) , programação em java

[PhTixa]

Boa Noite Galera! 
Estou com um dúvida em programação java!
O Trabalho é para desenvolver um quebra cabeça de 8 peças, e montar uma Busca em Profundidade, Largura, Gulosa e A*!
Mas estou com problemas de cara na Busca em profundidade pois ela está com estados repetidos!
Se alguém poder me ajudar realmente ficarei Muito Grato!
essa é a parte da Busca em Profundidade em que não estou entendendo o porque de não tratar esses estados! 
 

 

public ArrayList<Estado> EmProfun(Estado atual){
        Stack<Estado> pilha = new Stack<>();
        pilha.push(atual);
        
        while(!pilha.isEmpty()){
            Estado no = pilha.pop();
            
            if(no.VerificaOFinal()){
                System.out.println("Caminho:" +caminho.toString());
                System.out.println("Contador: "+count);
                caminho.add(no);
                return caminho;
            }
            
                if((! pilha.contains(no))){
                System.out.println("Entrou");    
                GeradordeEstados  ge = new GeradordeEstados(no.getEstadoAtual());
                pilha.addAll(ge.proximoPasso());
                caminho.add(no);
                count++;
                
                
            }
        }
        
        return null;
    }

Mais abaixo deixo o código para poderem ver melhor a minha situação valeu ai...

BuscaemLargura.java

BuscaEmProfundidade.java

Estado.java

GeradordeEstados.java

Interface.java

Matriz.java

[Thyago Henrique Pacher]

estou precisando desses algoritmos pode anexar novamente. Tenho o mesmo trabalho para entregar, e tal qual como você a dúvida não é em programação mas sim como estruturar o algoritmo para chegar lá. E o pior de tudo que acho mil exemplos simples de busca em largura mas nenhum com quebra cabeça de 8 peças.