from arbol import Nodo
 
def buscar_solucion_BFS(estado_inicial, solucion):
    solucionado = False
    nodos_visitados = []
    nodos_frontera = []
    nodoInicial = Nodo(estado_inicial)
    nodos_frontera.append(nodoInicial)
    while(not solucionado) and len(nodos_frontera) != 0:
        nodo = nodos_frontera.pop(0)
        #extraer nodo y anadirlo a visitados
        nodos_visitados.append(nodo)
        if nodo.get_datos() == solucion:
            #solucion encontrada
            solucionado = True
            return nodo
        else:
            #expandir nodos hijos
            dato_nodo = nodo.get_datos()
 
            #operador izquierdo
            hijo = [dato_nodo[1], dato_nodo[0], dato_nodo[2], dato_nodo[3]]
            hijo_izquierdo = Nodo(hijo)
            if not hijo_izquierdo.en_lista(nodos_visitados) and not hijo_izquierdo.en_lista(nodos_frontera):
                nodos_frontera.append(hijo_izquierdo)
                #operador central
                hijo = [dato_nodo[0], dato_nodo[2], dato_nodo[1], dato_nodo[3]]
                hijo_central = Nodo(hijo)
                if not hijo_central.en_lista(nodos_visitados) and not hijo_central.en_lista(nodos_frontera):
                    nodos_frontera.append(hijo_central)
                    #operador derecho
                    hijo = [dato_nodo[0], dato_nodo[1], dato_nodo[3], dato_nodo[2]]
                    hijo_derecho = Nodo(hijo)
                    if not hijo_derecho.en_lista(nodos_visitados) and not hijo_derecho.en_lista(nodos_frontera):
                        nodos_frontera.append(hijo_derecho)
 
                        nodo.set_hijos([hijo_izquierdo, hijo_central, hijo_derecho])
 
 
if __name__ == "__main__":
    estado_inicial = [4, 2, 3, 1]
    solucion = [1, 2, 3, 4]
    nodo_solucion = buscar_solucion_BFS(estado_inicial, solucion)
        #mostrar resultado
    resultado = []
    nodo = nodo_solucion
    while nodo.get_padre() != None:
        resultado.append(nodo.get_datos())
        nodo = nodo.get_padre()
    resultado.append(estado_inicial)
    resultado.reverse()
 
    print resultado