Los algoritmos de búsqueda en un espacio de estados pueden ser aplicados para resolver problemas de optimización discreta. El propósito de dichos algoritmos es encontrar una solución óptima que sea extremo de una función objetivo. En la mayoría de los casos, este tipo de problemas tiene una gran demanda de procesamiento, ya que el espacio de búsqueda se vuelve exponencial, por lo que es imprescindible resolverlos en forma paralela. Se investigó el problema del Puzzle N2-1, generalización del problema propuesto por Sam Lloyd, y se estudió el algoritmo de búsqueda A*. Basado en dicho algoritmo, se presenta una solución secuencial al problema del puzzle y se realiza la paralelización sobre una arquitectura tipo cluster utilizando la librería MPI.Eje: Redes académicasFacultad de Informática