Hola.

alquien comento aca este problema y me propuse a resolverlo

ahora bien mi pregunta es:

Mi algoritmo sera eficiente;
estos son los parametros que le mando a la funcion pero me resuelve el problema en 15  pasos,
ahora lo probe el mismo problema en una pagina de internet que resuelve este tipo de problemas y lo resuelve en 14 pasos asi que no se que pensar.

que no esta siendo eficiente del todo no?

int main(int argc, char** argv) 
{
	string inicio = "835416270";
 
	printf ("Prueba n1\n");
	string  meta = "123804765";
	intel(meta, inicio);
 
	printf("Ejemplo 2\n");
	meta = "216408753";
	intel(meta, inicio);
	return 0;
}

aca el ejemplo



aca mi salida que indica que se realizo en 15 pasos.



una pregunta mas en que tengo que basarme para indicar si mi algoritmo es bueno, en el tiempo de ejecucion que llevo en resolver el problema, o en el algoritmo que estoy implementando?

saludos muchas gracias.

Hola si tienes mucha razon lo que muestro de codigo no es nada para saber si mi algoritmo es eficiente no, el problema es que ya preguntaron aca por este ejercicio como una tarea y si subo el codigo le estare haciendo la tarea.

Pero entiendo bien lo que tratas de decir. en cuanto a que hace el programa es buscar la mejor solucion o la ruta mas corta para solucionar el problema, y en cuantos pasos se resuelve un juego Puzzle 8.

como puedes notar en esta parte de codigo le indico el problema desordenado que seria 835416270
y como lo quiero ordenado seria 123804765 para hacer esto lo realiza en 15 pasos.

tomando el 0 como espacio vacio y donde se van moviendo los demas numero para quedar ordenados.

string inicio = "835416270";
printf ("Prueba n1\n");
string  meta = "123804765";

muchas gracias por responder saludos : ).

Usas heurística o abres un árbol?

Salud

Asi es como comenta ivancea96

Hola aca esta el codigo para que me aconsegen

saludos y gracias por responder

#include <iostream>
#include <stdio.h>
#include <map>
#include <string>
#include<queue>
#include <cstdlib>
 
using namespace std;
 
class Nodo
{
	public:
		int profundidad, est;
		string str;
 
		Nodo (string str1, int profundidad1, int est1)
		{
			str = str1; //Estado
			profundidad = profundidad1; //Profundidad
			est = est1; // valor de evaluacion
		}
};
 
class Profundidad
{
	public: 
	int profundida, est;
	string prev;
 
	Profundidad(string prev1, int profundida1, int est1)
	{
		prev = prev1;  //Estado anterior
		profundida = profundida1; //Profundidad
		est = est1; //Valor de evaluacion
	}
};
 
bool operator< (Nodo n1, Nodo n2)
{
	bool sw = true;
	if(n1.est == n2.est)
		sw = (n1.str < n2.str) ? true:false;
 
	else
		sw = (n1.est > n2.est) ? true:false;
 
	return sw;
}
 
//Evaluacion del nodo
//profundidad
//str: estada
//Meta: estado objetivo
 
int estimacion(int profundida, string str, string meta)
{
	int i1, i2, i3, i4, k1, k2, pi = profundida, ws;
	char cg[3][3], cn[3][3];
 
	for (i1 =0; i1<9; i1++)
	{
		k1 = i1/3;
		k2 = i1 - 3 * k1;
		cg[k1][k2] = meta.at(i1) - '0';
	}
	for(i1 =0; i1 < 9; i1++)
	{
		k1 = i1 /3;
		k2 = i1 -3 * k1;
		cn[k1][k2] = str.at(i1) - '0';
	}
 
	for(i1 =0; i1 < 3; i1++)
	{
		for(i2 =0; i2 < 3; i2++)
		{
			ws = 1;
			for(i3 =0; i3 < 3 && ws > 0; i3++)
			{
				for(i4 =0; i4 < 3 && ws >0; i4++)
				{
					if(cg[i3][i4] == cn[i1][i2])
					{
						ws = 0;
						pi += (abs(i3-i1) + abs(i4-i2));
					}
				}
			}
		}
	}
 
	if (cn[1][1] != '0')
		pi++;
 
	if (cn[0][1] != (cn[0][0]+1)%9)
		pi +=2;
 
	if (cn[0][2] != (cn[0][1]+1)%9)
		pi +=2;
 
	if (cn[1][2] != (cn[0][2]+1)%9)
		pi +=2;
 
	if (cn[2][2] != (cn[1][2]+1)%9)
		pi +=2;
 
	if (cn[2][1] != (cn[2][2]+1)%9)
		pi +=2;
 
	if (cn[2][0] != (cn[2][1]+1)%9)
		pi +=2;
 
	if (cn[1][0] != (cn[2][0]+1)%9)
		pi +=2;
 
	if (cn[0][0] != (cn[1][0]+1)%9)
		pi +=2;
 
	return pi;
}
 
int mover (string str, string *res)
{
	int k, n = 0;
	string str1;
 
	k = str.find("0");
	switch(k)
	{
		case 0:
			str1 = str.replace(k, 1, str, k+3, 1);
			str1 = str1.replace(k+3, 1, 1, '0');
			res[n]  = str1;
			n++;
			str1 = str.replace(k, 1, str, k+1, 1);
			str1 = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
 
		case 1:
			str1 = str.replace(k, 1, str, k+3, 1);
			str1 = str1.replace(k+3, 1, 1, '0');
			res[n]  = str1;
			n++;
			str1 = str.replace(k, 1, str, k-1, 1);
			str1 = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			str1 = str.replace(k, 1, str, k+1, 1);
			str1 = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
 
		case 2:
			str1 = str.replace(k, 1, str, k+3, 1);
			str1 = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1 = str.replace(k, 1, str, k-1, 1);
			str1 = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
 
		case 3:
			str1 = str.replace(k, 1, str, k-3, 1);
			str1 = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1 = str.replace(k, 1, str, k+3, 1);
			str1 = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1 = str.replace(k, 1, str, k+1, 1);
			str1 = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
 
		case 4:
			str1 = str.replace(k, 1, str, k-3, 1);
			str1 = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1 = str.replace(k, 1, str, k+3, 1);
			str1 = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1 = str.replace(k, 1, str, k-1, 1);
			str1 = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			str1 = str.replace(k, 1, str, k+1, 1);
			str1 = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
 
		case 5:
			str1 = str.replace(k, 1, str, k-3, 1);
			str1 = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1 = str.replace(k, 1, str, k+3, 1);
			str1 = str1.replace(k+3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1 = str.replace(k, 1, str, k-1, 1);
			str1 = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
 
		case 6:
			str1 = str.replace(k, 1, str, k-3, 1);
			str1 = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1 = str.replace(k, 1, str, k+1, 1);
			str1 = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
 
		case 7:
			str1 = str.replace(k, 1, str, k-3, 1);
			str1 = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1 = str.replace(k, 1, str, k-1, 1);
			str1 = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			str1 = str.replace(k, 1, str, k+1, 1);
			str1 = str1.replace(k+1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
 
		case 8:
			str1 = str.replace(k, 1, str, k-3, 1);
			str1 = str1.replace(k-3, 1, 1, '0');
			res[n] = str1;
			n++;
			str1 = str.replace(k, 1, str, k-1, 1);
			str1 = str1.replace(k-1, 1, 1, '0');
			res[n] = str1;
			n++;
			break;
	}
 
	return n;
}
 
//Inicial
// Meta
 
void intel(string inicio, string meta)
{
	int i1, n, nodo1 = 1, nodo2 =0, profundida =1, ct =1, est;
	string str, res[4];
	priority_queue<Nodo> p;
	map<string, Profundidad> m;
	map<string, Profundidad>::iterator it;
	bool sw;
 
	est = estimacion(profundida, inicio, meta);
	m.insert(pair<string, Profundidad>(inicio, Profundidad("", profundida, est)));
	p.push(Nodo(inicio, profundida, est));
	while (!p.empty())
	{
		str = p.top().str;
		profundida = p.top().profundidad;
		nodo2++;
 
		//Objetivos
		if(str == meta)
		{
			ct = profundida;
			break;
		}
		//Si no hay una meta
		//A~nadidi a la cola, tienen el mismo status y mover el marco
		else
		{
			p.pop();
			n = mover(str, res);
 
			for (i1 =0; i1 < n; i1++)
			{
				sw = true;
				est = estimacion(profundida+1, res[i1], meta);
				it = m.find(res[i1]);
 
				if(it != m.end())
				{
					if(est < ((*it).second).est)
						m.erase(it);
 
					else
						sw = false;
				}
 
				if (sw)
				{
					m.insert(pair<string, Profundidad>(res[i1], Profundidad(str, profundida+1, est)));
					p.push(Nodo(res[i1], profundida+1, est));
					nodo1++;
				}
			}
		}
	}
 
	//Salida
	printf("Implementacion %d %d, Distancia minima %d\n", nodo1, nodo2, ct);
 
	while(str.length()>0)
	{
		printf("\n      %c %c %c\n", str.at(0), str.at(1), str.at(2));
		printf("      %c %c %c\n", str.at(3), str.at(4), str.at(5));
		printf("      %c %c %c\n", str.at(6), str.at(7), str.at(8));
		it = m.find(str);
		str = ((*it).second).prev;
	}
}
 
int main(int argc, char** argv) 
{
	string inicio = "835416270";
 
	printf ("Prueba n1\n");
	string  meta = "123804765";
	intel(meta, inicio);
 
	printf("Ejemplo 2\n");
	meta = "216408753";
	intel(inicio, meta);
	return 0;
}